Balanced Tunnel
Contest: Codeforces Global Round 5
Difficulty rating: 1300
Tags: data structures, sortings, two pointers

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 format:
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 format:
Output the number of cars to be fined.

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Note:
The first example is depicted below:

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.

Example input:
5
3 5 2 1 4
4 3 2 5 1

Example output:
2

Example input:
7
5 2 3 6 7 1 4
2 3 6 7 1 4 5

Example output:
6

Editorial:
This problem can be approached in several ways, here is one of them.
Let's say that cars exit the tunnel at time moments $$$1, 2, \ldots, n$$$, and let $$$c_i$$$ be time when car $$$a_i$$$ exited the tunnel.
For instance, in the first example we had $$$a = \langle 3, 5, 2, 1, 4 \rangle$$$ and $$$b = \langle 4, 3, 2, 5, 1 \rangle$$$. Then, $$$c = \langle 2, 4, 3, 5, 1 \rangle$$$: car $$$3$$$ entered first and exited at time $$$2$$$, so $$$c_1 = 2$$$; car $$$5$$$ entered second and exited and time $$$4$$$, so $$$c_2 = 4$$$; and so on.
Note that $$$c$$$ is a permutation, and not only it can be found in $$$O(n)$$$, but also it can be very useful for us. It turns out that we can use $$$c$$$ to easily determine if car $$$a_i$$$ must be fined.
Specifically, car $$$a_i$$$ must be fined if $$$c_i$$$ is smaller than $$$\max(c_1, c_2, \ldots, c_{i-1})$$$.
Why is that? Recall that car $$$a_i$$$ must be fined if there exists a car that entered the tunnel earlier and exited the tunnel later. If a car entered the tunnel earlier, it must be $$$a_j$$$ such that $$$j < i$$$. If a car exited the tunnel later, it must be that $$$c_j > c_i$$$.
Therefore, now we can just go from left to right, keeping the maximum of $$$c_1, c_2, \ldots, c_{i-1}$$$ to compare it to $$$c_i$$$. The overall complexity is $$$O(n)$$$.