配点 : $500$ 点

問題文

$1, 2, \ldots, N$ を並び替えた数列 $P = P_1, P_2, \ldots, P_N$ があります。

あなたは $P$ に対して、以下の $N - 1$ 種類の操作を、任意の順番でちょうど 1 回ずつ行わなければなりません。

• $P_1$ と $P_2$ を入れ替える
• $P_2$ と $P_3$ を入れ替える $\vdots$
• $P_{N - 1}$ と $P_N$ を入れ替える

操作の順番を適切に決めることで、$P$ を昇順に並び替えてください。 もしそれが不可能な場合、-1 を出力してください。

制約

• 入力は全て整数
• $2 \leq N \leq 2 \times 10^5$
• $P$ は $1, 2, \ldots, N$ を並び替えた数列

入力

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

$N$

$P_1$ $P_2$ $\ldots$ $P_N$

出力

どのような順番で操作しても $P$ を昇順に並び替えることができない場合、-1 を出力せよ。

$P$ を昇順に並び替えることができる場合、そのような操作列を $N - 1$ 行使って出力せよ。 $i \sim (1 \leq i \leq N - 1)$ 行目には、$i$ 回目の操作で $P_j$ と $P_{j + 1}$ を入れ替えるとして、$j$ を出力せよ。

$P$ を昇順に並び替える操作列が複数存在する場合、どれを出力しても構わない。

5
2 4 1 5 3

4
2
3
1

以下のような操作列が $P$ を昇順に並び替えます。

• まず $P_4$ と $P_5$ を入れ替える。$P$ は $2, 4, 1, 3, 5$ になる
• 次に $P_2$ と $P_3$ を入れ替える。$P$ は $2, 1, 4, 3, 5$ になる
• 次に $P_3$ と $P_4$ を入れ替える。$P$ は $2, 1, 3, 4, 5$ になる
• 次に $P_1$ と $P_2$ を入れ替える。$P$ は $1, 2, 3, 4, 5$ になる

5
5 4 3 2 1

-1