| Автор: | Всероссийская олимпиада школьников 2005 | Ограничение времени: | 1 сек | |
| Входной файл: | necklace.in | Ограничение памяти: | 64 Мб | |
| Выходной файл: | necklace.out |
В витрине ювелирного магазина стоит манекен, на шею которого надето ожерелье. Оно состоит из N колечек, нанизанных на замкнутую нить. Все колечки имеют разные размеры. В зависимости от размера колечки пронумерованы числами от 1 до N, начиная с самого маленького и до самого большого. Колечки можно передвигать вдоль нити и протаскивать одно через другое, но только в том случае, если номера этих колечек отличаются более чем на единицу.
Продавец хочет упорядочить колечки так, чтобы они располагались по возрастанию номеров вдоль нити по часовой стрелке. Снимать ожерелье с манекена нельзя.
Требуется написать программу, которая по заданному начальному расположению колечек находит последовательность протаскиваний колечек одно через другое, приводящую исходное расположение колечек в желаемое.
В первой строке входного файла записано число N.
Во второй строке через пробел следуют N различных чисел от 1 до N - номера колечек, расположенных вдоль нити по часовой стрелке.
Выходной файл должен содержать описание процесса упорядочения.
В каждой строке, кроме последней, должны быть записаны через пробел два числа, указывающие номера колечек, протаскиваемых друг через друга. В последней строке должен стоять ноль.
Количество строк выходного файла не должно превышать 50000.
Если требуемого упорядочения колечек достичь не удается, в выходной файл нужно вывести одно число -1.
| № | Входной файл (necklace.in) |
Выходной файл (necklace.out) |
|---|---|---|
| 1 | |
|