Codeforces Global Round 5
B
Balanced Tunnel
Codeforces
1300
原题
← AC1 →
翻译中…

Consider a tunnel on a one-way road. During a particular day, $n$ cars numbered from $1$ to $n$ entered and exited the tunnel exactly once. All the cars passed through the tunnel at constant speeds.

翻译中…

A traffic enforcement camera is mounted at the tunnel entrance. Another traffic enforcement camera is mounted at the tunnel exit. Perfectly balanced.

翻译中…

Thanks to the cameras, the order in which the cars entered and exited the tunnel is known. No two cars entered or exited at the same time.

翻译中…

Traffic regulations prohibit overtaking inside the tunnel. If car $i$ overtakes any other car $j$ inside the tunnel, car $i$ must be fined. However, each car can be fined at most once.

翻译中…

Formally, let's say that car $i$ definitely overtook car $j$ if car $i$ entered the tunnel later than car $j$ and exited the tunnel earlier than car $j$. Then, car $i$ must be fined if and only if it definitely overtook at least one other car.

翻译中…

Find the number of cars that must be fined.

翻译中…

Input

翻译中…

The first line contains a single integer $n$ ($2 \le n \le 10^5$), denoting the number of cars.

翻译中…

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$), denoting the ids of cars in order of entering the tunnel. All $a_i$ are pairwise distinct.

翻译中…

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le n$), denoting the ids of cars in order of exiting the tunnel. All $b_i$ are pairwise distinct.

翻译中…

Output

翻译中…

Output the number of cars to be fined.

翻译中…

Note

翻译中…

The first example is depicted below:

翻译中…

image

翻译中…

Car $2$ definitely overtook car $5$, while car $4$ definitely overtook cars $1$, $2$, $3$ and $5$. Cars $2$ and $4$ must be fined.

翻译中…

In the second example car $5$ was definitely overtaken by all other cars.

翻译中…

In the third example no car must be fined.

翻译中…

样例

Input #1
5
3 5 2 1 4
4 3 2 5 1
Output #1
2
InputCopy OutputCopy
Input #2
7
5 2 3 6 7 1 4
2 3 6 7 1 4 5
Output #2
6
InputCopy OutputCopy
Input #3
2
1 2
1 2
Output #3
0
InputCopy OutputCopy
题目信息
题号
1237B
时间限制
1 s
内存限制
512 MB
标签
数据结构
排序
双指针

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。