Codeforces Round 119 (Div. 1)
A
Permutations
Codeforces
1500
原题
←B →
翻译中…

Happy PMP is freshman and he is learning about algorithmic problems. He enjoys playing algorithmic games a lot.

翻译中…

One of the seniors gave Happy PMP a nice game. He is given two permutations of numbers $1$ through $*n*$ and is asked to convert the first one to the second. In one move he can remove the last number from the permutation of numbers and inserts it back in an arbitrary position. He can either insert last number between any two consecutive numbers, or he can place it at the beginning of the permutation.

翻译中…

Happy PMP has an algorithm that solves the problem. But it is not fast enough. He wants to know the minimum number of moves to convert the first permutation to the second.

翻译中…

Input

翻译中…

The first line contains a single integer $*n*$ ($1 ≤ *n* ≤ 2·10^{5}$) — the quantity of the numbers in the both given permutations.

翻译中…

Next line contains $*n*$ space-separated integers — the first permutation. Each number between $1$ to $*n*$ will appear in the permutation exactly once.

翻译中…

Next line describe the second permutation in the same format.

翻译中…

Output

翻译中…

Print a single integer denoting the minimum number of moves required to convert the first permutation to the second.

翻译中…

Note

翻译中…

In the first sample, he removes number 1 from end of the list and places it at the beginning. After that he takes number 2 and places it between 1 and 3.

翻译中…

In the second sample, he removes number 5 and inserts it after 1.

翻译中…

In the third sample, the sequence of changes are like this:

翻译中…
  • 1 5 2 3 4
  • 1 4 5 2 3
  • 1 3 4 5 2
  • 1 2 3 4 5
翻译中…

So he needs three moves.

翻译中…

样例

Input #1
3
3 2 1
1 2 3
Output #1
2
InputCopy OutputCopy
Input #2
5
1 2 3 4 5
1 5 2 3 4
Output #2
1
InputCopy OutputCopy
Input #3
5
1 5 2 3 4
1 2 3 4 5
Output #3
3
InputCopy OutputCopy
题目信息
题号
187A
时间限制
2 s
内存限制
256 MB
标签
贪心

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