Background

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

Problem Description

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

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

5
3 1 4 2 5

1
1 5

8
2 4 1 5 3 6 7 8

2
2 6
1 2

2
2 1

3
1 1
2 2
1 2

Hint

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.

Translated by ChatGPT 5