Description:
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 Format:
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 Format:
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$$$).
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.