← 返回题目列表

AtCoder · arc110_c

C. 额外交换

中文机器翻译题面 查看原题

分数: 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