Problem Background

Translated from ROI 2018 Day2 T2. Быстрая сортировка (Quick sort).

Problem Description

Given a permutation of $n$ elements $[a_1, a_2, \ldots, a_n]$.
Define the operation $S(l, r)$ as: rearrange the subsequence $[a_l, a_{l+1}, \ldots, a_r]$ into $[a_{l+1}, a_{l+3}, \ldots, a_l, a_{l+2}, \ldots]$.
For example: $[2, 4, 1, 5, 3, 6, 7, 8] \xrightarrow{S(2,6)} [2, 1, 3, 4, 5, 6, 7, 8]$, where the substring $[4, 1, 5, 3, 6]$ is rearranged into $[1, 3, 4, 5, 6]$.
Given a permutation, determine the number of operations required to sort the permutation in ascending order and output any set of operations. It is not required to minimize the number of operations, but the number of operations must be $\leq 15000$.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers representing the permutation $a$.

Output Format

The first line contains an integer $k$, representing the number of operations. It must satisfy $0 \leq k \leq 15000$.

The next $k$ lines describe the operations in order. For each operation, output two integers $L$ and $R$, indicating that the subsequence $a_L, a_{L+1}, \ldots, a_R$ is operated on. It must satisfy $1 \leq L \leq R \leq n$.

Note that you do not need to minimize $k$. You only need to ensure $0 \leq k \leq 15000$. It is guaranteed that such a $k$ exists.

Sample Input and Output

Sample Input #1

5
3 1 4 2 5

Sample Output #1

1
1 5

Sample Input #2

8
2 4 1 5 3 6 7 8

Sample Output #2

2
2 6
1 2

Sample Input #3

2
2 1

Sample Output #3

3
1 1
2 2
1 2

Notes

Let $k_0$ denote the minimum number of operations.

For all data, $1 \leq n \leq 3000$, $0 \leq k_0 \leq 15000$, $1 \leq a_i \leq n$, and $a_i$ are distinct.

见题面 Input 部分

见题面 Output 部分