Two Reversals

A board contains the numbers from 1 to N in order from left to right. One operation chooses an interval [i, j] and reverses the order of every number in that interval. Here i <= j, and reversing [i, i] is allowed and changes nothing.

For instance, when N = 10, the initial board is:

If interval [3, 8] is reversed, the board becomes:

If interval [1, 5] is then reversed, the board becomes:

You are given the state of a board after two interval reversals have been applied to the initial board. Find two intervals to reverse, in order, so that applying them to the given board restores the initial order 1, 2, 3, ..., N.

There may be multiple valid answers. In that case, output any one of them.

The first line contains the integer N (5 <= N <= 10000), the size of the board.

The next line contains N integers: the state of the board after two interval reversals.

Print two lines. Each line must contain two integers i and j, describing the interval [i, j] to reverse. The two intervals are applied in the order printed.

A valid answer is guaranteed to exist.