Array Rotation

Time limit

10s

Memory limit

128 MB

Problem

An array initially contains the natural numbers from 1 to N in order. The following array shows the case N=6.


1	2	3	4	5	6

You may choose any interval (a, b) and rotate it once. A rotation reverses the order of the numbers from position a through position b, and also changes the sign of every number in that interval. (1 ≤ a ≤ b ≤ N) If the interval (1, 4) is rotated in the array above, the result is as follows.


-4	-3	-2	-1	5	6

The same operation can be applied repeatedly to an array that has already been rotated. If interval (3, 5) is then rotated, the final array becomes:


-4	-3	-5	1	2	6

The initial array is always the ordered array 1 through N. Given a final array state, write a program that constructs that final array from the initial array using a small number of rotation operations.

Input

The first line contains the array size N (1 ≤ N ≤ 250). The second line contains the final array state in order, separated by spaces. For each value from 1 through N, exactly one number with that absolute value appears in the sequence.

Output

On the first line, print K, the number of rotation operations used. Then print K lines in the order the operations are performed. Each line contains two integers a and b, the interval (a, b) to rotate. (1 ≤ a ≤ b ≤ N)