← 返回题目列表

Codeforces · 584/E

E. 安东和艾拉

中文机器翻译题面 查看原题

Anton 喜欢通过用金钱交换元素来将一种排列转变为另一种排列,而 Ira 不喜欢为愚蠢的游戏付费。帮助他们通过支付尽可能少的钱来获得所需的排列。

更正式地说,我们有两种排列,即从 1 到 n 的数字的 p 和 s。我们可以通过支付 |i - j| 来交换 pi 和 pj硬币。找出并打印从排列 p 获得排列 s 所需的最小硬币数。还打印我们获得解决方案的交换操作序列。

输入

第一行包含一个数字 n (1 ≤ n ≤ 2000) — 排列的长度。

第二行包含从 1 到 n 的 n 个数字的序列 — 排列 p。从 1 到 n 的每个数字在此行中只出现一次。

第三行包含从 1 到 n 的 n 个数字的序列 — 排列 s。从 1 到 n 的每个数字在此行中出现一次。

输出

在第一行中打印将排列 p 转换为排列 s 所需花费的最小硬币数量。

在第二行中打印数字 k (0 ≤ k ≤ 2·106) — 获得解所需的操作数。

在接下来的 k 行中打印操作。每行必须包含两个数字 i 和 j (1 ≤ i, j ≤ n, i ≠ j),这意味着需要交换 pi 和 pj。

保证解存在。

示例

输入 #1

4
4 2 1 3
3 2 4 1

输出 #1

3
2
4 3
3 1

注意

在第一个样本测试中,我们交换位置 3 和 4 上的数字,排列 p 变为 4 2 3 1。我们支付 |3 - 4| = 1 个硬币。在第二回合,我们交换位置 1 和 3 上的数字,得到等于 s 的排列 3241。我们支付 |3 - 1| = 2 个硬币。我们总共支付了三枚硬币。