Three Reversals

Time limit1sMemory limit128 MB

Summary

Given an array formed by reversing three intervals of 1..N, find three interval reversals (with trivial ones allowed) that restore it to sorted order.

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

Problem

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.

Input

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

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.

Examples1

Example 1
Input
```
10
6 7 8 2 1 9 3 4 5 10
```
Expected output
```
6 9
1 5
3 8
```