配点 : 100 点
問題文
海老间桑 我有 (1,\ 2,\ ...,\ N) 的排列 给出了 (P_1,\ P_2,\ ...,\ P_N) 并想按升序对其进行排序。
Ebima-san可以根据需要多次执行以下操作。 1 也可以根本不执行该操作。 交换
- P_i 和 按字典顺序比较 P_j 。这时候的费用 支付 |i-j| 。
此时,请找出使Ebima付出的成本最小的操作程序,以升序重新排列顺序。
制約
- 1 \leq N \leq 2000
- 1 \leq P_i \leq N
- i \neq j 如果 P_i \neq P_j
入力
输入是按以下格式从标准输入给出的。
N P_1 P_2 \cdots P_N
出力
1 在第一行,输出操作数,直到 Ebima 按升序重新排列排列。
i+1 线 i Ebima-san 进行第二次手术。 假设你想交换 P_{S_i} 和 按字典顺序比较 P_{T_i} , 输出 S_i 和 按字典顺序比较 T_i 以空格分隔。
如果有多个符合问题陈述条件的操作程序,则输出哪一个并不重要。
M S_1 T_1 S_2 T_2 \vdots S_M T_M
入力例 1
3 3 1 2
出力例 1
2 1 2 2 3
第一 1 项目和 2 交换物品,然后 2 项目和 3 交换物品可以降低总成本。 2 ,这是最小值。
入力例 2
10 3 7 10 1 9 5 4 8 6 2
出力例 2
11 3 4 5 6 2 3 6 7 1 2 4 6 7 9 6 7 7 10 3 7 2 3