Bubble sort

ID 34881. Necklace

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
 

ID 38576. "Sorting" with candy

An array of N different natural numbers from 1 to N is given. works as follows. First, the first and second elements are compared, and if the first is greater than the second, then they are swapped. Then the same procedure is carried out with the second and third element, …, with the penultimate and last. Then this procedure is repeated again with the first and second, with the second and third, …, with the penultimate and last elements. And so (N & ndash; 1) times.

Sorting "with candy" is performed according to the same rules, but additionally given a list of pairs of numbers that do not change with each other under any conditions (in this case, the sorter gets a candy for missing the corresponding exchange). For example, the presence of a pair (4,1) in the list means that if at some point the numbers 4 and 1 or 1 and 4 are nearby, and according to the sorting algorithm they need to be swapped, then the exchange will not happen, and the sorter will get candy .

It is required to sort "with candy" given array and return the sort result.

Input
First enter the number N — the number of numbers in the array, then N numbers — array elements. Next, the number M — the number of pairs of numbers for which they give a candy, and then M pairs of numbers. If there is a pair (i,j) in the list, then the pair (j,i) also gets candy.

1≤ N≤ 5000.0≤ M≤ 10000.

Imprint
It is required to display the array after sorting.

Examples