Endless Journey

convertible

Background

Once upon a time, there was a child named Kino who loved to travel and had been to many strange and wonderful places. One day, he arrived at a large bridge and found many convertibles parked on it. Unfortunately, the bridge was very narrow, allowing only one convertible to pass at a time. However, the cars on the bridge would not yield to each other, causing traffic from both directions to become stuck and unable to move.

Later, the builders added a new feature to the bridge: the ability to rotate a certain segment of the bridge by 180 degrees, which causes the convertibles on that segment to flip their orientation and reverse their order, as shown in the figure below:

Figure 1. Convertibles 321 after rotation form 123

As shown in the figure above, the convertibles 321 met the convertibles 45 on the bridge, causing a traffic jam. At this point, we can rotate the segment containing 321, so that the order of the convertibles on the bridge becomes 12345, and they all face the same direction, allowing them to drive off the bridge. Of course, this is just a simple example; the situation on the actual bridge is much more complex and requires multiple rotations to reach the 12345 configuration.

However, after designing the bridge, the designer went on a trip, and none of the remaining residents knew how to operate this magical bridge. As a result, the situation on the bridge became increasingly chaotic until, finally, it reached its current state. Now, in order to cross the bridge, Kino found the control device and the manual by the bridge and rediscovered how to operate it. With the help of nearby residents, he successfully arranged the convertibles on the bridge into the order 1, 2, 3, ..., $n$, all facing the same direction. Do you know how he did it?

Input

This is an answer-submission problem. The input files convertible1.in through convertible10.in are already provided in the user directory. The first line of the input file contains the number of convertibles $n$ on the bridge, with car IDs $1, 2, \dots, n$. The second line contains the positions and directions of the convertibles on the bridge, represented by a sequence of $+i$ or $-i$. A value of $-i$ at the $j$-th position indicates that convertible $i$ is at the $j$-th position on the bridge and is facing right, while a value of $+i$ at the $j$-th position indicates that convertible $i$ is at the $j$-th position on the bridge and is facing left.

Output

You should place the output files convertible1.out through convertible10.out in the user directory; you do not need to submit a program. The first line of the output file should contain the number of rotations $m$. The following $m$ lines should each describe a rotation, including the left boundary position and the right boundary position. Your output must ensure that the final sequence is $1, 2, 3, \dots, n$, and not $-1, -2, -3, \dots, -n$ or anything else.

Examples

Input 1

5
-3 -2 -1 4 5

Output 1

1
1 3

Subtasks

Each test case is worth 10 points. Your score depends on the ratio of your result to the reference answer.

Note

This problem provides an output checker convertible_c. Run it as follows: ./convertible_c 3 This checks if convertible3.out is valid.