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