CF1237B.Balanced Tunnel
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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.
输入格式
The first line contains a single integer n ( 2≤n≤105 ), denoting the number of cars.
The second line contains n integers a1,a2,…,an ( 1≤ai≤n ), denoting the ids of cars in order of entering the tunnel. All ai are pairwise distinct.
The third line contains n integers b1,b2,…,bn ( 1≤bi≤n ), denoting the ids of cars in order of exiting the tunnel. All bi are pairwise distinct.
输出格式
Output the number of cars to be fined.
输入输出样例
输入#1
5 3 5 2 1 4 4 3 2 5 1
输出#1
2
输入#2
7 5 2 3 6 7 1 4 2 3 6 7 1 4 5
输出#2
6
输入#3
2 1 2 1 2
输出#3
0
说明/提示
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.