Ukje and Mysophobia

Interview

Time limit2sMemory limit256 MB

Summary

Sort a permutation of 1 to N by repeatedly reversing intervals, using at most N*N reversals to make card i sit at position i.

Level: Medium6 of 10
Topics: Array, Sorting, Implementation, Greedy
Solved: No attempts yet

Problem

You are given $N$ cards in a row, holding each integer from $1$ to $N$ exactly once. You may choose any interval $[L, R]$ with $1 \le L < R \le N$ and reverse the whole interval. For instance, reversing $[2, 5]$ in $[1, 5, 10, 15, 20, 25]$ yields $[1, 20, 15, 10, 5, 25]$ .

Number positions from the left. The target arrangement has number $i$ on card $i$ for every $i$ . Apply operations to maximize the number of cards that match the target arrangement. Every permutation can be sorted by reversals alone, so the maximum is always $N$ .

Input

The first line gives the number of cards $N$ ( $1 \le N \le 1000$ ).

The second line gives the initial arrangement as $N$ integers from left to right.

Output

Print the number of operations $op$ on the first line. It must satisfy $op \le N \times N$ .

On each of the next $op$ lines, print the interval $[L, R]$ used, with $L$ and $R$ separated by a single space. If $op$ is $0$ , print nothing more. Applying all operations in order must produce the target arrangement.

Examples3

Example 1
Input
```
5
2 1 5 4 3
```
Expected output
```
2
3 5
1 2
```
Example 2
Input
```
5
5 2 1 4 3
```
Expected output
```
2
1 3
3 5
```
Example 3
Input
```
1
1
```
Expected output
```
0
```