问题6393--拍照2

6393: 拍照2

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MiB

题目描述

这是一个似乎很熟悉的情况,Farmer John 正在将他的 N 头编号为 1…N 的奶牛(1≤N≤105)排成一排,以便拍照。

最初,奶牛从左到右按a1,a2,…,aN 的顺序排列。Farmer John 的目标是将奶牛从左到右按b1,…,bN 的顺序排列。为此,他可以对排序进行一系列修改操作。每次修改操作可以选择一头奶牛并将其向左移动一些位置。

请计算 Farmer John 将奶牛排列成所要求的顺序所需的最小修改次数。

输入格式(从终端 / 标准输入读入):

输入的第一行包含 N。第二行包含 a1,a2,…,aN。第三行包含 b1,b2,…,bN

输出格式(输出至终端 / 标准输出):

输出将奶牛排列成所要求的顺序所需的最小修改次数。

输入样例:

5

1 2 3 4 5

1 2 3 4 5

输出样例:

0

在这个例子中,奶牛已经排列成所要求的顺序,所以无需进行修改操作。

输入样例:

5

5 1 3 2 4

4 5 2 1 3

输出样例:

2

在这个例子中,两次修改操作足够了。以下是一种 Farmer John 重新排列他的奶牛们的方式:

选择奶牛 44 并将其向左移动四个位置。

选择奶牛 22 并将其向左移动两个位置。

   5 1 3 2 4

-> 4 5 1 3 2

-> 4 5 2 1 3

测试点性质:

测试点 3-6 满足 N≤100

测试点 7-10 满足N≤5000

测试点 11-14 没有额外限制。

供题:Benjamin Qi

 

输入

输入的第一行包含 N。第二行包含 a1,a2,…,aN。第三行包含 b1,b2,…,bN

输出

输出将奶牛排列成所要求的顺序所需的最小修改次数。

样例输入 复制

5
1 2 3 4 5
1 2 3 4 5

样例输出 复制

0

提示

测试点性质:

测试点 3-6 满足 N≤100。

测试点 7-10 满足N≤5000。

测试点 11-14 没有额外限制。

来源/分类