問題文

時は 20XX 年，世界は Distributed AtC◯der 社の支配によるディストピアである．現在，人々の娯楽は分散・並列処理を題材としたプログラミングコンテストに限られている．例えば，週末に家族でスーパーコンピュータを (ssh で) 訪れるというのはとてもよく見られる光景である． （問題文参考: UTPC 2011 問題 A）

（実際のところ以下で述べる問題設定は分散というより並列処理で Distributed Sorting というより Parallel Sorting っぽいのだが，頭文字が D の方が都合がいいし，ここで言い訳もしていることだし，とにかく今日はクリスマスなので我々は細かいことは気にしない．）

分散・並列処理においては，基礎的と思える処理でも多種多様な工夫が考えられることが多くある．たとえば，N 個の相異なる整数からなる整数列 X_1, X_2, ..., X_N を昇順にソートする処理を考えよう．

ソートには，以下の 1 種類の操作が可能なマシンを用いるとする．

• 操作: 2k 個の相異なるインデックス A_1, A_2, ..., A_{2k} を入力として与えると，各 i (1 \leq i \leq k) に対し X_{A_{2i-1}} と X_{A_{2i}} (X の A_{2i-1} 番目と A_{2i} 番目) の値を交換する．ただし，各 j (1 \leq j \leq 2k) に対し 1 \leq A_j \leq N でなければならない．

たとえば X = (5, 3, 1, 2, 4) のとき k=2，(A_1, A_2, A_3, A_4) = (1, 3), (2, 4) として操作を行うと，X = (1, 2, 5, 3, 4) になる．

この操作だけを使って X を昇順にソートするために必要な操作の最小回数を求め，実際にその最小回数の操作で X をソートする手順をひとつ出力するようなプログラムを作成せよ．

制約

• 1 \leq N \leq 10^5．
• 1 \leq X_i \leq 10^9．
• X_i は相異なる整数．

入力例 1

3
2 3 1

出力例 1

2
1 1 3
1 2 3

操作の回数が最小であり，正しく昇順にソートできるような手順であれば，これ以外の出力でも正解と見なされる．たとえばこの入力例に対しては

2
1 1 2
1 3 1

のような出力も正解と見なす．

入力例 2

3
1 2 3

出力例 2

0

入力例 3

5
5 4 3 2 1

出力例 3

1
2 1 5 2 4