CF584E Anton and Ira

Anton 喜欢通过花钱交换元素，将一个排列变成另一个排列，而 Ira 并不喜欢为这种“无聊的游戏”买单。请帮助他们用尽可能少的钱得到需要的排列。 更正式地说，现有两个排列 $p$ 和 $s$，它们均为 $1$ 到 $n$ 的一个排列。你可以交换 $p_i$ 和 $p_j$，为此需要支付 $|i-j|$ 个硬币。请你求出将排列 $p$ 变为 $s$ 至少需要支付多少个硬币，并输出实现方案时操作的顺序。

第一行包含一个整数 $n$（$1 \le n \le 2000$），表示排列的长度。 第二行包含 $n$ 个 $1$ 到 $n$ 的整数，表示排列 $p$。这一行中的每个整数从 $1$ 到 $n$，且每个出现一次。 第三行包含 $n$ 个 $1$ 到 $n$ 的整数，表示排列 $s$。这一行中的每个整数从 $1$ 到 $n$，且每个出现一次。

第一行输出一个整数，表示将排列 $p$ 变成 $s$ 所需支付的最小硬币数。 第二行输出一个整数 $k$（$0 \le k \le 2 \cdot 10^{6}$），表示实现方案需要的交换操作次数。 接下来的 $k$ 行，每行输出两个整数 $i$ 和 $j$（$1 \le i,j \le n$，$i \ne j$），表示将 $p_i$ 和 $p_j$ 交换。 保证一定存在解。

在第一个样例测试中，我们交换第 3 和第 4 位，排列 $p$ 变为 $4\ 2\ 3\ 1$，花费 $|3-4|=1$ 个硬币。第二次交换第 1 和第 3 位，得到排列 $3\ 2\ 4\ 1$，这与 $s$ 相等，花费 $|3-1|=2$ 个硬币。总共花费 3 个硬币。 由 ChatGPT 5 翻译