Задача F. Ожерелье.

Имя входного файла: input.txt
Имя выходного файла: output.txt
Максимальное время работы на одном тесте: 1 секунды
Максимальный объем используемой памяти: 64 мегабайта
В витрине ювелирного магазина стоит манекен, на шею которого надето ожерелье. Оно состоит из N колечек, нанизанных на замкнутую нить. Все колечки имеют разные размеры. В зависимости от размера колечки пронумерованы числами от 1 до N, начиная с самого маленького и до самого большого. Колечки можно передвигать вдоль нити и протаскивать одно через другое, но только в том случае, если номера этих колечек отличаются более чем на единицу.
Продавец хочет упорядочить колечки так, чтобы они располагались по возрастанию номеров вдоль нити по часовой стрелке. Снимать ожерелье с манекена нельзя.
Требуется написать программу, которая по заданному начальному расположению колечек находит последовательность протаскиваний колечек одно через другое, приводящую исходное расположение колечек в желаемое.

Формат входных данных:

Первая строка входных данных содержит число N (2 ≤ N ≤ 50).
Во второй строке через пробел следуют N различных чисел от 1 до N - номера колечек, расположенных вдоль нити по часовой стрелке.

Формат выходных данных:

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

Пример

Пример вводаПример вывода
4
3 2 4 1

1 3
2 4
1 4
0