In the window of a jewelry store, there is a mannequin with a necklace around its neck. It consists of N rings strung on a closed thread. All rings are different sizes. Depending on the size, the rings are numbered from 1 to N, starting from the smallest to the largest. Rings can be moved along the thread and dragged one through the other, but only if the numbers of these rings differ by more than one.
The seller wants to arrange the rings so that they are arranged in ascending numbers along the thread in a clockwise direction. You cannot remove the necklace from the mannequin.
It is required to write a program that, given the initial arrangement of the rings, finds a sequence of dragging the rings one through the other, bringing the initial arrangement of the rings to the desired one.
Input
The first line of the input contains number N (2 ≤ N ≤ 50).
The second line contains N different numbers from 1 to N — numbers of rings arranged clockwise along the thread.
Imprint
Your program should output a description of the ordering process.
In each line of the output data, except for the last one, two numbers should be written separated by a space, indicating the numbers of the rings being dragged through each other. The last line must be zero.
The number of output lines should not exceed 50000.
If the required ordering of the rings cannot be achieved, the program should output a single number –1
| Input |
Output |
4
3 1 2 4
| 4 2
4 1
0 |