题目详情
返回题库题目描述
在一个熟悉的情景中，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$。
说明/提示
- 测试用例 3-6 满足 $N \leq 100$。
- 测试用例 7-10 满足 $N \leq 5000$。
- 测试用例 11-14 没有额外限制。
输出描述
输出将奶牛排列成目标顺序所需的最少修改次数。
提示
样例解释 1
在这个例子中，奶牛已经处于目标顺序，因此不需要任何修改。
样例解释 2
在这个例子中，两次修改即可满足要求。以下是 Farmer John 重新排列奶牛的一种方式：
- 选择奶牛 $4$ 并将其向左移动四个位置。
- 选择奶牛 $2$ 并将其向左移动两个位置。