/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 ~ (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
Score : 500 points
Problem Statement
We have a permutation P = P_1, P_2, \ldots, P_N of 1, 2, \ldots, N.
You have to do the following N - 1 operations on P, each exactly once, in some order:
-
Swap P_1 and P_2.
-
Swap P_2 and P_3.
\vdots
-
Swap P_{N-1} and P_N.
Your task is to sort P in ascending order by configuring the order of operations.
If it is impossible, print -1 instead.
Constraints
- All values in input are integers.
- 2 \leq N \leq 2 \times 10^5
- P is a permutation of 1, 2, \ldots, N.
Input
Input is given from Standard Input in the following format:
N P_1 P_2 \ldots P_N
Output
If it is impossible to sort P in ascending order by configuring the order of operations, print -1.
Otherwise, print N-1 lines to represent a sequence of operations that sorts P in ascending order. The i-th line (1 \leq i \leq N - 1) should contain j, where the i-th operation swaps P_j and P_{j + 1}.
If there are multiple such sequences of operations, any of them will be accepted.
Sample Input 1
5 2 4 1 5 3
Sample Output 1
4 2 3 1
The following sequence of operations sort P in ascending order:
- First, swap P_4 and P_5, turning P into 2, 4, 1, 3, 5.
- Then, swap P_2 and P_3, turning P into 2, 1, 4, 3, 5.
- Then, swap P_3 and P_4, turning P into 2, 1, 3, 4, 5.
- Finally, swap P_1 and P_2, turning P into 1, 2, 3, 4, 5.
Sample Input 2
5 5 4 3 2 1
Sample Output 2
-1