H. 并行交换排序

每次测试时间限制：7 秒
内存限制：1024 MB

---

你有一个排列 $p_1, p_2, \dots, p_n$，它是 $[1,2,\dots,n]$ 的一个排列。你可以进行若干次（可能为零次）如下操作：

• 选择一个长度为偶数的子数组 $[l, r]$；
• 交换 $a_l$ 与 $a_{l+1}$；
• 交换 $a_{l+2}$ 与 $a_{l+3}$（如果 $l+3 \le r$）；
• …
• 交换 $a_{r-1}$ 与 $a_r$。

请在最多 $10^6$ 次操作内将排列排序。你不需要最小化操作次数。

---

输入

第一行包含一个整数 $n$（$2 \le n \le 3 \cdot 10^5$）——排列的长度。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$，所有 $p_i$ 互不相同）——初始排列。

---

输出

按以下格式输出你的操作。

第一行包含一个整数 $k$（$0 \le k \le 10^6$）——操作次数。

接下来的 $k$ 行依次描述每个操作。每行包含两个整数 $l$ 和 $r$（$1 \le l < r \le n$，且 $r-l+1$ 必须是偶数）——表示这次操作选择子数组 $[l, r]$，并按照题目描述交换其中的元素。

所有操作结束后，必须对每个 $i$（$1 \le i \le n$）满足 $a_i = i$。

---

示例

输入

5
2 5 4 1 3

输出

5
1 4
1 2
2 5
1 4
4 5

输入

9
1 2 3 4 5 6 7 8 9

输出

0

输入

10
6 4 2 3 8 10 9 1 5 7

输出

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)$，得到 $[5,2,1,4,3]$。
• 第二次操作选择 $[l,r]=[1,2]$，交换 $(a_1,a_2)$，得到 $[2,5,1,4,3]$。
• 第三次操作选择 $[l,r]=[2,5]$，交换 $(a_2,a_3)$ 和 $(a_4,a_5)$，得到 $[2,1,5,3,4]$。
• 第四次操作选择 $[l,r]=[1,4]$，交换 $(a_1,a_2)$ 和 $(a_3,a_4)$，得到 $[1,2,3,5,4]$。
• 第五次操作选择 $[l,r]=[4,5]$，交换 $(a_4,a_5)$，得到 $[1,2,3,4,5]$，已排序。

在第二个样例中，排列已经有序，因此不需要任何操作。