分数: 500 点
问题陈述
我们有一个排列 P = P_1, P_2, \ldots, P_N of 1, 2, \ldots, N.
您必须执行以下操作 N - 1 操作 P, 每个恰好一次,按某种顺序:
-
交换 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.
否则,打印 N-1 行表示排序的操作序列 P 按升序排列。 的 i第行 (1 \leq i \leq N - 1) 应包含 j,其中 i-th 操作交换 P_j 和 P_{j + 1}.
如果有多个这样的操作序列,则其中任何一个都将被接受。
示例输入 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