P9291 [ROI 2018] Quick sort

Translated from [ROI 2018 Day2](https://neerc.ifmo.ru/school/archive/2017-2018.html) T2. [Быстрая сортировка ](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day2.pdf) ([Quick sort](http://codeforces.com/gym/102154/problem/C)).

You are given a permutation $[a_1,a_2,\ldots,a_n]$ of length $n$. Define an operation $S(l,r)$ as follows: rearrange the segment $[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 subarray $[4, 1, 5, 3, 6]$ is rearranged into $[1, 3, 4, 5, 6]$. Given a permutation, find how many operations are needed to make it increasing, and output any valid sequence of operations. You do $not$ need to minimize the number of operations, but you must ensure the number of operations is $\leq 15000$.

The first line contains an integer $n$. The second line contains $n$ integers, representing the permutation $a$.

The first line contains an integer $k$, the number of operations you perform. It must satisfy $0 \leq k \leq 15000$. In the next $k$ lines, describe your operations in order. For each step, output two integers $L$, $R$, meaning you apply the operation once to the segment $a_L,a_{L+1},\ldots,a_R$. It must satisfy $1 \leq L \leq R \le n$. Note that you do **not** need to minimize $k$. You only need to guarantee $0 \le k \leq 15000$. It is guaranteed that such a $k$ exists.

Let $k_0$ be the minimum number of operations. For all testdata, $1\leq n\leq 3000$, $0\leq k_0\leq 15000$, $1\leq a_i\leq n$, and all $a_i$ are distinct. | Subtask ID | $n$ | Special property | | :-----------: | :-----------: | :-----------: | | $1$ | $1 \leq n \leq 100$ | $k_0 = 1$ | | $2$ | $1 \leq n \leq 100$ | None | | $3$ | $1 \leq n \leq 1000$ | None | | $4$ | $1 \leq n \leq 3000$ | None | Translated by ChatGPT 5