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 个硬币。我们总共支付了三枚硬币。