E - Min Cost Sort Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

えびまさんは (1,\ 2,\ ...,\ N) の順列 (P_1,\ P_2,\ ...,\ P_N) を持っていて、これを昇順に並び替えたいと考えています。

えびまさんは、以下の操作を好きな回数だけ行うことができます。 1 回も操作を行わないことも可能です。

  • P_i と P_j をスワップする。この時、コスト |i-j| を支払う。

この時、えびまさんが順列を昇順に並び替えるまでに支払うコストが最小となる様な操作手順を求めてください。

制約

  • 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 行目にえびまさんが順列を昇順に並び替えるまでの操作回数を出力せよ。

i+1 行目に i 回目の操作でえびまさんが 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