21741번 - Ожерелье 스페셜 저지다국어

В витрине ювелирного магазина стоит манекен, на шею которого надето ожерелье. Оно состоит из N колечек, нанизанных на замкнутую нить. Все колечки имеют разные размеры. В зависимости от размера  колечки пронумерованы числами от 1 до N, начиная с самого маленького и до самого большого. Колечки можно передвигать вдоль нити и протаскивать  одно через другое, но только в том случае, если номера этих колечек отличаются более чем на единицу. 

Продавец хочет упорядочить колечки так, чтобы они располагались по возрастанию номеров вдоль нити по часовой стрелке. Снимать ожерелье с манекена нельзя.

Требуется написать программу, которая по заданному начальному расположению колечек находит последовательность протаскиваний колечек одно через другое, приводящую исходное расположение колечек в желаемое.

В первой строке входного файла записано число N (2 ≤ N ≤ 50). 

Во второй строке через пробел следуют N различных чисел от 1 до N — номера колечек, расположенных вдоль нити по часовой стрелке. 

Выходной файл должен содержать описание процесса упорядочения.

В каждой строке, кроме последней, должны быть записаны через пробел два числа, указывающие номера колечек, протаскиваемых друг через друга. В последней строке должен стоять ноль.

Количество строк выходного файла не должно превышать 50000.

Если требуемого упорядочения колечек достичь не удается, в выходной файл нужно вывести одно число  –1.