CF1909H Parallel Swaps Sort

[Dubmood - Keygen 8](https://soundcloud.com/penehlopeexd/keygen-8-dubmood) ⠀ 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.

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 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 $ ).

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.