← 返回题目列表

Codeforces · 187/A

A. 排列

中文机器翻译题面 查看原题

Happy PMP是新生,他正在学习算法问题。他非常喜欢玩算法游戏。

一位学长给兴欣PMP打了一场精彩的比赛。给他两个数字 1 到 n 的排列,并要求他将第一个排列转换为第二个排列。只需一步,他就可以从数字排列中删除最后一个数字,并将其插回任意位置。他可以在任意两个连续数字之间插入最后一个数字,也可以将其放在排列的开头。

Happy PMP 有一个算法可以解决这个问题。但它还不够快。他想知道将第一个排列转换为第二个排列所需的最少步数。

输入

第一行包含一个整数 n (1 ≤ n ≤ 2·105) — 两个给定排列中的数字数量。

下一行包含 n 个空格分隔的整数 — 第一个排列。 1 到 n 之间的每个数字在排列中只会出现一次。

下一行以相同的格式描述第二个排列。

输出

打印一个整数,表示将第一个排列转换为第二个排列所需的最小移动次数。

示例

输入 #1

3
3 2 1
1 2 3

输出 #1

2

输入 #2

5
1 2 3 4 5
1 5 2 3 4

输出 #2

1

输入 #3

5
1 5 2 3 4
1 2 3 4 5

输出 #3

3

注意

在第一个示例中,他从列表末尾删除数字 1 并将其放在开头。之后,他将数字 2 放在 1 和 3 之间。

在第二个示例中,他删除了数字 5 并将其插入到 1 之后。

在第三个示例中,更改顺序如下:

- 1 5 2 3 4
- 1 4 5 2 3
- 1 3 4 5 2
- 1 2 3 4 5