消除交叉(Eliminate Crossings)

题目描述

一条大河分南北岸，两岸各有 $N$ 座码头。码头之间有 $N$ 条航线，航线的编号为 $1$ 到 $N$。一座码头只能通行一条航线。

航线之间存在交叉，容易产生撞船事故。我们需要调整一些航线的起点与终点，消除所有交叉。

管理部门只允许调整起点相邻或终点相邻的两条航线。即：

• 如果两条航线的起点是相邻的，可以交换这两条航线的起点。
• 如果两条航线的终点是相邻的，可以交换这两条航线的终点。

请问最少需要调整几次，才能消除所有航线之间的交叉？

输入格式

第一行：单个整数表示 $n$。

第二行：$n$ 个整数表示 $x_1, x_2, \cdots, x_n$，其中 $x_i$ 表示北岸第 $i$ 号码头是第 $x_i$ 号航线的起点；

第三行：$n$ 个整数表示 $y_1, y_2, \cdots, y_n$，其中 $y_i$ 表示南岸第 $i$ 号码头是第 $y_i$ 号航线的终点。

输出格式

单个整数：表示消除所有交叉点需要的最少调整次数。

样例输入 #1

4
4 2 1 3
1 3 4 2

样例输出 #1

4

数据范围

• 对于 30% 的分数，$n \le 1000$；
• 对于 60% 的分数，$n \le 10000$；
• 对于 100% 的分数，$1 \le n \le 100000$。

知识点与难度

本题涉及的知识点从属于 GESP 5级（逆序对、归并排序），难度等级：⭐⭐⭐。