Dubmood - 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 \lt 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.

Parallel Swaps Sort

Examples