cho.shTime limit
1s
Memory limit
128 MB
There is a board whose cells contain the numbers from 1 to N in order. Initially, the board reads 1, 2, ..., N from left to right.
| Cell | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
An interval [i, j] means all cells from the i-th cell through the j-th cell from the left. It is always true that i <= j. In one operation, you may choose one interval and reverse the order of all numbers inside it.
For N = 10, reversing interval [3, 8] in the initial state changes the board as follows.
| Cell | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Number | 1 | 2 | 8 | 7 | 6 | 5 | 4 | 3 | 9 | 10 |
If interval [1, 5] is then reversed, followed by interval [6, 9], the board becomes the following states in order.
| Cell | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Number | 6 | 7 | 8 | 2 | 1 | 5 | 4 | 3 | 9 | 10 |
| Cell | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Number | 6 | 7 | 8 | 2 | 1 | 9 | 3 | 4 | 5 | 10 |
You are given the state of a board after three interval reversals. Find three intervals to reverse, in order, so that applying them to the given board restores the initial state 1, 2, 3, ..., N.
If several triples of intervals work, you may output any one of them. Reversing [i, i] changes nothing, and such intervals are allowed.
The first line contains the board size N (5 <= N <= 1000).
The second line contains N integers separated by spaces, representing the board after three interval reversals.
Output the three intervals that should be reversed, in order, to restore the given board to the initial state.
Print three lines. Each line must contain two integers i and j, separated by a space, representing an interval [i, j]. A valid answer always exists.