← 返回题目列表

AtCoder · monamieHB2021_e

E. 最小成本排序

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

配点 : 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