В витрине ювелирного магазина стоит манекен, на шею которого надето ожерелье. Оно состоит из N колечек, нанизанных на замкнутую нить. Все колечки имеют разные размеры. В зависимости от размера колечки пронумерованы числами от 1 до N, начиная с самого маленького и до самого большого. Колечки можно передвигать вдоль нити и протаскивать одно через другое, но только в том случае, если номера этих колечек отличаются более чем на единицу.
Продавец хочет упорядочить колечки так, чтобы они располагались по возрастанию номеров вдоль нити по часовой стрелке. Снимать ожерелье с манекена нельзя.
Требуется написать программу, которая по заданному начальному расположению колечек находит последовательность протаскиваний колечек одно через другое, приводящую исходное расположение колечек в желаемое.
Входные данные
Первая строка входных данных содержит число N (2 ≤ N ≤ 50).
Во второй строке через пробел следуют N различных чисел от 1 до N — номера колечек, расположенных вдоль нити по часовой стрелке.
Выходные данные
Ваша программа должна вывести описание процесса упорядочения.
В каждой строке выходных данных, кроме последней, должны быть записаны через пробел два числа, указывающие номера колечек, протаскиваемых друг через друга. В последней строке должен стоять ноль.
Количество выводимых строк не должно превышать 50000.
Если требуемого упорядочения колечек достичь не удается, программа должна вывести одно число –1
| Ввод |
Вывод |
4
3 1 2 4 |
4 2
4 1
0 |