310920: CF1909H. Parallel Swaps Sort

H. Parallel Swaps Sorttime limit per test7 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputDubmood - Keygen 8⠀

You are given a permutation $p_1, p_2, \dots, p_n$ of $[1, 2, \dots, n]$. You can perform the following operation some (possibly $0$) times:

• choose a subarray $[l, r]$ of even length;
• swap $a_l$, $a_{l+1}$;
• swap $a_{l+2}$, $a_{l+3}$ (if $l+3 \leq r$);
• $\dots$
• swap $a_{r-1}$, $a_r$.

Sort the permutation in at most $10^6$ operations. You do not need to minimize the number of operations.

Input

The first line contains a single integer $n$ ($2 \le n \le 3 \cdot 10^5$) — the length of the permutation.

The second line contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$, the $p_i$ are distinct) — the permutation before performing the operations.

Output

Output your operations in the following format.

The first line should contain an integer $k$ ($0 \le k \le 10^6$) — the number of operations.

The next $k$ lines represent the $k$ operations in order. Each of these $k$ lines should contain two integers $l$ and $r$ ($1 \leq l < r \leq n$, $r-l+1$ must be even) — the corresponding operation consists in choosing the subarray $[l, r]$ and swapping its elements according to the problem statement.

After all the operations, $a_i = i$ must be true for each $i$ ($1 \leq i \leq n$).

ExamplesInput

5
2 5 4 1 3

Output

5
1 4
1 2
2 5
1 4
4 5

Input

9
1 2 3 4 5 6 7 8 9

Output

0

Input

10
6 4 2 3 8 10 9 1 5 7

Output

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

Note

In the first test:

• At the beginning, $p = [2, 5, 4, 1, 3]$.
• In the first operation, you can choose $[l, r] = [1, 4]$. Then, $(a_1, a_2)$ are swapped and $(a_3, a_4)$ are swapped. The new permutation is $p = [5, 2, 1, 4, 3]$.
• In the second operation, you can choose $[l, r] = [1, 2]$. Then, $(a_1, a_2)$ are swapped. The new permutation is $p = [2, 5, 1, 4, 3]$.
• In the third operation, you can choose $[l, r] = [2, 5]$. Then, $(a_2, a_3)$ are swapped and $(a_4, a_5)$ are swapped. The new permutation is $p = [2, 1, 5, 3, 4]$.
• In the fourth operation, you can choose $[l, r] = [1, 4]$. Then, $(a_1, a_2)$ are swapped and $(a_3, a_4)$ are swapped. The new permutation is $p = [1, 2, 3, 5, 4]$.
• In the fifth operation, you can choose $[l, r] = [4, 5]$. Then, $(a_4, a_5)$ are swapped. The new permutation is $p = [1, 2, 3, 4, 5]$, which is sorted.

In the second test, the permutation is already sorted, so you do not need to perform any operation.

题目大意：给定一个长度为n的排列p，可以通过选择一个长度为偶数的子数组[l, r]，并按规则进行元素交换，来对排列进行排序。规则是交换al和al+1，al+2和al+3，依此类推，直到ar-1和ar。要求在最多10^6次操作内完成排序。

输入数据格式：第一行包含一个整数n（2 ≤ n ≤ 3 * 10^5），表示排列的长度。第二行包含n个整数p1, p2, ..., pn（1 ≤ pi ≤ n，且pi各不相同），表示初始排列。

输出数据格式：第一行包含一个整数k（0 ≤ k ≤ 10^6），表示操作的次数。接下来k行，每行包含两个整数l和r（1 ≤ l < r ≤ n，且r-l+1为偶数），表示选择的子数组。按照题目规则进行交换后，排列必须满足ai = i（1 ≤ i ≤ n）。

示例：

输入：
5
2 5 4 1 3

输出：
5
1 4
1 2
2 5
1 4
4 5

解释：在第一次操作中，选择子数组[1, 4]，交换(a1, a2)和(a3, a4)，得到排列[5, 2, 1, 4, 3]。依此类推，最终得到排序后的排列[1, 2, 3, 4, 5]。题目大意：给定一个长度为n的排列p，可以通过选择一个长度为偶数的子数组[l, r]，并按规则进行元素交换，来对排列进行排序。规则是交换al和al+1，al+2和al+3，依此类推，直到ar-1和ar。要求在最多10^6次操作内完成排序。 输入数据格式：第一行包含一个整数n（2 ≤ n ≤ 3 * 10^5），表示排列的长度。第二行包含n个整数p1, p2, ..., pn（1 ≤ pi ≤ n，且pi各不相同），表示初始排列。 输出数据格式：第一行包含一个整数k（0 ≤ k ≤ 10^6），表示操作的次数。接下来k行，每行包含两个整数l和r（1 ≤ l < r ≤ n，且r-l+1为偶数），表示选择的子数组。按照题目规则进行交换后，排列必须满足ai = i（1 ≤ i ≤ n）。 示例： 输入： 5 2 5 4 1 3 输出： 5 1 4 1 2 2 5 1 4 4 5 解释：在第一次操作中，选择子数组[1, 4]，交换(a1, a2)和(a3, a4)，得到排列[5, 2, 1, 4, 3]。依此类推，最终得到排序后的排列[1, 2, 3, 4, 5]。