CF1909H Parallel Swaps Sort

你有一个排列 $p_1, p_2, \dots, p_n$，它是 $[1, 2, \dots, n]$ 的一个排列。你可以进行如下操作若干次（也可以一次都不做）： - 选择一个偶数长度的子数组 $[l, r]$； - 交换 $a_l$ 和 $a_{l+1}$； - 如果 $l+3 \leq r$，则交换 $a_{l+2}$ 和 $a_{l+3}$； - $\dots$ - 交换 $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$ 行，每行两个整数 $l$ 和 $r$（$1 \leq l < r \leq n$，$r-l+1$ 必须为偶数），表示一次操作。每次操作选择子数组 $[l, r]$ 并按题意交换其元素。 所有操作后，要求对于每个 $i$（$1 \leq i \leq n$），都有 $a_i = i$。

在第一个测试样例中： - 初始时，$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]$，排列已排序。 在第二个测试样例中，排列已经有序，因此不需要进行任何操作。 由 ChatGPT 4.1 翻译