题目描述

$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 を出力してください。

输入格式

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

$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$ を昇順に並び替える操作列が複数存在する場合、どれを出力しても構わない。

题目大意

一个长度为 $N$ 的序列，有 $N-1$ 次机会交换相邻两个数，且每两个位置上的数仅有一次机会进行交换，最终用完所有 $N-1$ 次交换使这个无序序列变为单调上升序列。如果可以，则按顺序输出每次交换的位置；如果不行，输出 $-1$。

5
2 4 1 5 3

4
2
3
1

5
5 4 3 2 1

-1

提示

制約

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

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