问题 N: 拍照 Photoshoot 2

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:112 通过:39

题目描述

Farmer John 正在将他的 N 头奶牛 ( 1≤N≤105 ) 排成一排,方便地编号为 1…N ,以便拍照。

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

请计算农民约翰按所需顺序排列奶牛所需的最少修改次数。

输入格式

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

输出格式

输出所需的最少修改次数。

输入样例 复制

5
5 1 3 2 4
4 5 2 1 3

输出样例 复制

2

数据范围与提示

输入样例1:

5
1 2 3 4 5
1 2 3 4 5

输出样例1:

0

样例1解释

本样例中,奶牛已经按照约翰满意的顺序排列,因此无需任何操作。

输入样例2:

5
5 1 3 2 4
4 5 2 1 3

输出样例2:

2

样例2解释

在本样例中,至少需要 2 次操作,具体如下:

  1. 让奶牛 4 向左移动 4 位。
  2. 让奶牛 2 向左移动 2 位。

队列变化如下:

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