Как опытный игрок, Вася одним движением руки может
взять несколько первых чисел колоды и вернуть их в обратном порядке. Например,
из колоды 1 2 3 4 5 6 (N
для этой колоды равно 6) Вася может
получить 4 3 2 1 5 6 (если изменит порядок четырёх
первых чисел).
Для получения чёрного пояса по игре в числа Васе
осталось научиться упорядочивать колоду. Используя только описанный приём, он
должен расположить все числа в колоде по возрастанию (самое первое число – 1,
второе – 2, ..., последнее – N). Задача усложняется тем, что упорядочивание колоды
нужно произвести не более чем за 2N переворотов. Напишите
обучающую программу для Васи.
В первой строке входных данных находится число N
(2 £ N £ 10),
количество чисел в колоде. Во второй строке находятся N
различных чисел через пробел, каждое от 1 до N, – числа в
колоде. Колода изначально не является упорядоченной. Выведите числа,
разделённые пробелами – последовательность переворотов, которая упорядочивает
колоду. Каждый переворот должен описываться числом от 2 до N.
Всего должно быть сделано не более 2N
переворотов.
Пример ввода
4
4 2
3 1
Пример вывода
3 2
3 4
Комментарий к примеру
Колода менялась так: 4 2 3 1
® 3 2 4 1, 3 2 4 1
® 2 3 4 1, 2 3 4 1
® 4 3 2 1, 4 3 2 1
® 1 2 3 4
