問題文

$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 ~ (1 \\leq i \\leq N - 1)$ 行目には、$i$ 回目の操作で $P_j$ と $P_{j + 1}$ を入れ替えるとして、$j$ を出力せよ。

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

入力例 1

5
2 4 1 5 3

出力例 1

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$ になる

入力例 2

5
5 4 3 2 1

出力例 2

-1