Замкнутая сортировка

Задан целочисленный массив A[1..N] из N различных чисел, в котором записана некоторая фиксированная перестановка чисел от 1 до N. Будем считать, что первый и последний элементы массива соединены таким образом, что за последним следует первый, а перед первым располагается последний. Мы получили замкнутую последовательность чисел без начала и конца.

Требуется отсортировать такой массив (упорядочить в нем элементы по возрастанию), при этом следует соблюдать следующие ограничения:

1. Разрешается менять местами только два соседних элемента массива.
2. Не разрешается менять местами элементы, если они отличаются ровно на единицу.

Например, если исходный массив из шести элементов имеет вид [2, 1, 3, 6, 4, 5], то мы должны получить в результате, например, такой массив: [4, 5, 6, 1, 2, 3]. В результате, правее каждого элемента должен стоять превосходящий его ровно на единицу, кроме N (справа от N должна быть единица).

Входные данные

Первая строка входного файла INPUT.TXT содержит целое число N – размер входного массива (2 ≤ N ≤ 50). Вторая строка содержит N целых чисел – исходную перестановку чисел от 1 до N в массиве.

Выходные данные

В выходной файл OUTPUT.TXT выведите K строк, где K – количество обменов в сортировке. На каждой строке выведите по два числа x_i и y_i, разделенных пробелом – значения меняемых элементов массива на i-м шаге. В последней строке выходных данных должен стоять 0. Помните, что должно выполняться условие |x_i–y_i| > 1 и что менять можно только соседние элементы массива. Если существует несколько решений, то разрешается вывести любое из них. Количество строк выходного файла не должно превышать 50 000. Если же такого решения не существует, то следует вывести «impossible» (без кавычек).

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки] [Решение]