I - そーっとソート Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

(1,\ 2,\ …,\ N) の順列として、数列 a_1,\ a_2,\ …,\ a_N が与えられます。

あなたは、以下の操作を 100,000 回まで行うことができます。

  • a_i と a_j の値を入れ替える。ただし、|i-j| = a_i または |i-j| = a_j を満たしていなければならない。

数列を 1,\ 2,\ …,\ N へと並び変えることが出来るか判定し、また、出来るならばその手順を 1 つ示してください。

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 a_2 … a_N
  • 1 行目には数列の要素数 N(1 \leq N \leq 50) が与えられる。
  • 2 行目には、数列の要素 a_i が空白区切りで与えられる。
  • a_1,\ a_2,\ ,…,\ a_N は (1,\ 2,\ …,\ N) の順列である。

出力

出力は標準出力に行い、末尾に改行を入れること。

もしどのような手順でも 100,000 回以内の操作では数列がソート出来ないならば、MuriyarokonnNaN と出力すること。

ソートすることが出来る場合は、以下の形式に従い出力すること。

R
X_1 Y_1
X_2 Y_2
:
X_R Y_R
  • 1 行目には操作の回数 R(0 \leq R \leq 100,000) を出力する。
  • 2 行目から R 行には操作の詳細を出力する。このうち i 行目には整数 X_i(1 \leq X_i \leq N),\ Y_i(1 \leq Y_i \leq N) を空白区切りで出力する。これは、i 回目の操作では a_{X_i} と a_{Y_i} の値を入れ替えることを表す。(修正,15:41)

入力例1

5
4 2 3 1 5

出力例1

(13:55)1行目の値に誤りがあり、修正しました。 

3
2 4
1 2
2 4