单身狗的序列

TimeLimit:2000MS  MemoryLimit:256MB
64-bit integer IO format:%I64d
未提交 | 登录后收藏
Problem Description

图片.png


今天是情人节,身为单身狗的Morning_X只能一个人窝在家里写题

大佬Home_W给了Morning_X一个排序的题目,题意是:


Home_W给出了两个数字1到n的排列,并要求Morning_X将第一个转换为第二个。

在一次移动中,Morning_X可以从数字排列中删除最后一个数字,并将其插入任意位置。 他可以在任何两个连续数字之间插入最后一个数字,也可以将其放置在排列的开头。


Morning_X狗粮吃多了, 现在蠢的不行,但是他还是想到了一个办法解决这个问题,但是他将这个问题转变一个方式来问你们,

问:将第一个排列转换为第二个排列的最小步数?


Input

The first line contains a single integer n (1 ≤ n ≤ 2·105) — 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.


第一个输入一个 整数n (1 ≤ n ≤ 2·105),代表接下来给出的两个序列的数字个数。


第二行输入n个整数,整数的大小在1-n之间,且不会出现重复数字。代表第一个序列


第三行输入同样格式的n个数字,代表第二个序列

Output

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

打印一个整数,代表将第一个序列转变成第二个序列的最小步数

SampleInput 1
3
3 2 1
1 2 3
SampleOutput 1
2
SampleInput 2
5
1 2 3 4 5
1 5 2 3 4
SampleOutput 2
1
SampleInput 3
5
1 5 2 3 4
1 2 3 4 5
SampleOutput 3
3
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.
Submit
题目统计信息详细
总AC数9
通过人数9
尝试人数10
总提交量14
AC率64.29%
AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题,请不要查看标签
如果您已经通过了该题,请务为该题贴上标签

T^T Online Judge

[BUG反馈] [FAQ] [闽ICP备17026590号-1]
当前版本:3.24 系统时间: