您将得到 $$$[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]$$$,已排序。
在第二个测试中,排列已经排序,因此您不需要执行任何操作。