← 返回题目列表

Codeforces · 1148/C

C. 疯狂钻石

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

给您一个从 $$$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]$$$。