Magic Stone Toy

Interview

Time limit1sMemory limit256 MB

Summary

Sort a permutation of 1..N into increasing order using at most 100 reversals of adjacent segments, or report impossible.

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

Problem

Legend says the power of the kingdom of Polymath flows from magic stones. A friend who sells magic stone toys has asked you to help tidy up the shop.

The shop has $N$ toys, and their sizes are distinct natural numbers from $1$ to $N$ . You want to sort the toys by size, so that from left to right their sizes are $1, 2, \cdots, N$ . To do this you may perform several operations. One operation is to choose several adjacent toys and reverse their order. For example, if the sizes from left to right are $1, 2, 5, 4, 3$ and you operate on the third through fifth toys, the sizes become $1, 2, 3, 4, 5$ from left to right, and the sorting is finished.

Write a program that decides whether the toys can be sorted in at most 100 operations, and if so, finds any way to do it.

Input

The first line gives the number of toys $N$ . The second line gives $N$ integers $A_1, A_2, \cdots, A_N$ representing the sizes of the toys, separated by spaces.

Output

If the toys cannot be sorted in at most 100 operations, print $-1$ and terminate the program. If they can be sorted, print the number of operations $Q$ on the first line. On each of the next $Q$ lines, print the left end index $l_i$ and the right end index $r_i$ of the toys affected by that operation. For example, if you operate on the third through fifth toys from the left, print $3$ $5$ .

Constraints

$1 \le N \le 100$
$1 \le A_i \le N$
$i \neq j \Leftrightarrow A_i \neq A_j$

If sorting is possible, the output must satisfy the following.

$0 \le Q \le 100$
$1 \le l_i \le r_i \le N$ $(1 \le i \le Q)$

Examples2

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