P8184 [USACO22FEB] Photoshoot 2 B

题目描述

在一个熟悉的情景中，Farmer John 正在为他的 $N$ 头奶牛（$1 \leq N \leq 10^5$，编号为 $1 \cdots N$）排队拍照。
初始时，奶牛从左到右的排列顺序为 $a_1, a_2, \cdots , a_N$。Farmer John 的目标是将奶牛从左到右排列成 $b_1, \cdots , b_N$ 的顺序。为了实现这一目标，他可以对排列顺序进行一系列修改。每次修改包括选择一头奶牛并将其向左移动若干位置。

请计算 Farmer John 将奶牛排列成目标顺序所需的最少修改次数。

输入格式

输入的第一行包含 $N$。第二行包含 $a_1, a_2, \cdots , a_N$。第三行包含 $b_1, \cdots , b_N$。

输出格式

输出将奶牛排列成目标顺序所需的最少修改次数。

样例解释 1

在这个例子中，奶牛已经处于目标顺序，因此不需要任何修改。

样例解释 2

在这个例子中，两次修改即可满足要求。以下是 Farmer John 重新排列奶牛的一种方式：

• 选择奶牛 $4$ 并将其向左移动四个位置。
• 选择奶牛 $2$ 并将其向左移动两个位置。

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

输入输出样例 1

5
1 2 3 4 5
1 2 3 4 5

0

输入输出样例 2

5
5 1 3 2 4
4 5 2 1 3

2

说明/提示

• 测试用例 3-6 满足 $N \leq 100$。
• 测试用例 7-10 满足 $N \leq 5000$。
• 测试用例 11-14 没有额外限制。