405897: GYM102154 C Quick sort

The scientists invented the new UL-2018 processor that is able to quickly process arrays in some special way. A key feature of its architecture is the separation operation of a segment of the array.

Consider an array $$$[a_1, a_2, \ldots, a_n]$$$. The separation operation is characterized by two integers $$$L$$$ and $$$R$$$. Let $$$S(L, R)$$$ denote the operation of the segment $$$[a_L, a_{L+1}, \ldots, a_R]$$$. Executing the $$$S(L, R)$$$ operation reorders the elements in this segment as follows. First, the elements $$$a_{L+1}, a_{L+3}, a_{L+5}, \ldots$$$ are taken, that is elements $$$a_i$$$ that $$$i - L$$$ is odd. Their relative order remains unchanged. Then, the elements $$$a_L, a_{L+2}, a_{L+4}, \ldots$$$ are taken ($$$a_i$$$ that $$$i - L$$$ is even). These retain the relative order too.

For example, consider the array $$$[2, 4, 1, 5, 3, 6, 7, 8]$$$. Applying the operation $$$S(2, 6)$$$ changes the segment $$$[4, 1, 5, 3, 6]$$$ into $$$[1, 3, 4, 5, 6]$$$, so the entire array becomes $$$[2, 1, 3, 4, 5, 6, 7, 8]$$$.

To demonstrate the capabilities of the new processor, the scientists decided to use separation operations to sort an array of distinct numbers. You will be given an array of size $$$n$$$ ($$$1 \le n \le 3\,000$$$) with distinct numbers from $$$1$$$ to $$$n$$$. You must sort it in ascending order using no more than $$$15\,000$$$ separation operations.

For example, the mentioned array $$$[2, 4, 1, 5, 3, 6, 7, 8]$$$ can be sorted in two separation operations. First, apply $$$S(2, 6)$$$ to get $$$[2, 1, 3, 4, 5, 6, 7, 8]$$$, and then the operation $$$S(1, 2)$$$ makes the array sorted increasingly: $$$[1, 2, 3, 4, 5, 6, 7, 8]$$$.

Your task is to write a program that for a given array determines the sequence of at most $$$15\,000$$$ separation operations, after which the specified array will be sorted in ascending order. It isn't necessary to minimize the number of operations performed (just use at most $$$15\,000$$$).

The first line of the input contains an integer $$$n$$$ — the number of elements in the given array ($$$1 \le n \le 3000$$$).

The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ — the elements of the given array ($$$1 \le a_i \le n$$$, all $$$a_i$$$ are different).

The first line of the output should contain an integer $$$k$$$ — the number of separation operations performed ($$$0 \le k \le 15\,000$$$).

In the following $$$k$$$ lines, you should print the description of the operations, in the order they are executed. Each operation is described by two integers $$$L$$$ and $$$R$$$ — the beginning and the end of the segment to which the separation operation should be applied ($$$1 \le L \le R \le n$$$).

Note that you don't have to minimize the number $$$k$$$. You can output any sequence of separation operations that contains at most $$$15\,000$$$ operations and sorts the given array in ascending order. It is guaranteed that at least one such sequence exists.

$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Subtask} & \text{Points} & \text{Constraints} & \text{Dependencies} \\ \hline 1 & 20 & n \le 100; \ \text{there is a solution with } k = 1 & \\ \hline 2 & 30 & n \le 100 & 0, 1 \\ \hline 3 & 30 & n \le 1\,000 & 0-2 \\ \hline 4 & 20 & n \le 3\,000 & 0-3 \\ \hline \end{array}$$$$$$

You will get points for a group if you pass all tests in this group and all groups listed in the dependencies. The group $$$0$$$ denotes the sample test(s) from the statement.

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

The second sample test is analyzed in detail in the problem statement.

In the third sample test, there is a solution with a single separation operation, but since you don't have to minimize the number of operations, the provided output is also correct.