给您一个从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$p$$$,其中 $$$n$$$ 是偶数。
您的目标是对排列进行排序。为此,您可以执行零个或多个以下类型的操作:
- 采用两个索引 $$$i$$$ 和 $$$j$$$ 使得 $$$2 \cdot |i - j| \geq n$$$ 并交换 $$$p_i$$$ 和 $$$p_j$$$。
无需最小化操作数量,但是您应该使用不超过 $$$5 \cdot n$$$ 操作。人们可以证明,这样做总是有可能的。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$, $$$n$$$ 是偶数) — 排列的长度。
第二行包含 $$$n$$$ 不同的整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) - 给定的排列。
输出
在第一行打印 $$$m$$$ ($$$0 \le m \le 5 \cdot n$$$) — 要执行的交换次数。
以下 $$$m$$$ 行中的每一行都应包含整数 $$$a_i, b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$|a_i - b_i| \ge \frac{n}{2}$$$) — 应在相应交换中交换的索引。
请注意,无需最小化操作数量。我们可以证明答案总是存在的。
示例
输入 #1
2 2 1
输出 #1
1 1 2
输入 #2
4 3 4 1 2
输出 #2
4 1 4 1 4 1 3 2 4
输入 #3
6 2 5 3 1 4 6
输出 #3
3 1 5 2 5 1 4
注意
在第一个示例中,当交换位置 $$$1$$$ 和 $$$2$$$ 上的元素时,数组将排序。
在第二个示例中,请注意无需最小化交换次数。
在第三个示例中,交换位置 $$$1$$$ 和 $$$5$$$ 上的元素后,数组变为:$$$[4, 5, 3, 1, 2, 6]$$$。交换位置 $$$2$$$ 和 $$$5$$$ 上的元素后,数组变为 $$$[4, 2, 3, 1, 5, 6]$$$,最后交换位置 $$$1$$$ 和 $$$4$$$ 上的元素后,数组变为已排序:$$$[1, 2, 3, 4, 5, 6]$$$。