← 返回题目列表

Codeforces · 1909/H

H. 并行交换排序

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

您将得到 $$$[1, 2, \dots, n]$$$ 的排列 $$$p_1, p_2, \dots, p_n$$$。您可以执行以下操作几次(可能是 $$$0$$$):

- 选择偶数长度的子数组$$$[l, r]$$$;
- 交换$$$a_l$$$,$$$a_{l+1}$$$;
- 交换 $$$a_{l+2}$$$, $$$a_{l+3}$$$ (如果 $$$l+3 \leq r$$$);
- $$$\点$$$
- 交换$$$a_{r-1}$$$、$$$a_r$$$。

在最多 $$$10^6$$$ 操作中对排列进行排序。您不需要最小化操作数量。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — 排列的长度。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$,$$$p_i$$$ 是不同的)— 执行操作之前的排列。

输出

按以下格式输出您的操作。

第一行应包含一个整数 $$$k$$$ ($$$0 \le k \le 10^6$$$) — 操作数。

接下来的 $$$k$$$ 行按顺序表示 $$$k$$$ 操作。这些 $$$k$$$ 行中的每一行都应包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l < r \leq n$$$,$$$r-l+1$$$ 必须为偶数)——相应的操作包括选择子数组 $$$[l, r]$$$ 并根据问题陈述交换其元素。

在所有操作之后,对于每个 $$$i$$$ ($$$1 \leq i \leq n$$$),$$$a_i = i$$$ 必须为真。

示例

输入 #1

5
2 5 4 1 3

输出 #1

5
1 4
1 2
2 5
1 4
4 5

输入 #2

9
1 2 3 4 5 6 7 8 9

输出 #2

0

输入 #3

10
6 4 2 3 8 10 9 1 5 7

输出 #3

15
1 8
6 9
1 8
3 10
1 10
1 10
1 6
6 9
6 9
2 7
9 10
5 10
1 6
2 9
1 10

注意

在第一个测试中:

- 开始时,$$$p = [2, 5, 4, 1, 3]$$$。
- 在第一个操作中,您可以选择 $$$[l, r] = [1, 4]$$$。然后,$$$(a_1, a_2)$$$ 被交换,$$$(a_3, a_4)$$$ 被交换。新的排列是 $$$p = [5, 2, 1, 4, 3]$$$。
- 在第二个操作中,您可以选择$$$[l, r] = [1, 2]$$$。然后,$$$(a_1, a_2)$$$ 被交换。新的排列是 $$$p = [2, 5, 1, 4, 3]$$$。
- 在第三个操作中,您可以选择$$$[l, r] = [2, 5]$$$。然后,$$$(a_2, a_3)$$$ 被交换,$$$(a_4, a_5)$$$ 被交换。新的排列是 $$$p = [2, 1, 5, 3, 4]$$$。
- 在第四个操作中,您可以选择$$$[l, r] = [1, 4]$$$。然后,$$$(a_1, a_2)$$$ 被交换,$$$(a_3, a_4)$$$ 被交换。新的排列是 $$$p = [1, 2, 3, 5, 4]$$$。
- 在第五个操作中,您可以选择$$$[l, r] = [4, 5]$$$。然后,$$$(a_4, a_5)$$$ 被交换。新的排列是 $$$p = [1, 2, 3, 4, 5]$$$,已排序。

在第二个测试中,排列已经排序,因此您不需要执行任何操作。