题目描述

有一个由 $1, 2, \ldots, N$ 组成的排列数列 $P = P_1, P_2, \ldots, P_N$。

你需要对 $P$ 进行以下 $N-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$ 行输出 $j$，表示第 $i$ 次操作是交换 $P_j$ 和 $P_{j+1}$。

如果存在多种可行的操作顺序，输出任意一种均可。

样例 1

输入

5
2 4 1 5 3

输出

4
2
3
1

样例 2

输入

5
5 4 3 2 1

输出

-1

说明/提示

限制条件

• 输入均为整数
• $2 \leq N \leq 2 \times 10^5$
• $P$ 是 $1, 2, \ldots, N$ 的一个排列

样例解释 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$

由 ChatGPT 4.1 翻译