ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1568. Сортировка вагонов

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В Екатеринбурге строится сразу несколько небоскрёбов. Для их возведения требуется много стройматериалов высокого качества, большинство из которых доставляется в город по железной дороге. И эта доставка не всегда происходит так быстро, как этого хотели бы подрядчики. Все дело в том, что составы слишком долго простаивают на узловых станциях, пока их сортируют для отправки в разные концы страны.
Как известно, товарные вагоны сортируются следующим образом: состав подгоняется к развилке, где каждый вагон может проследовать по левому или правому пути. После этого состав «склеивается». Например, если вагоны были в порядке «1 2 3 4 5 6 7», то можно разделить их на две части «1 3 5» (влево) и «2 4 6 7» (вправо), и затем склеить, получив «1 3 5 2 4 6 7».
Помогите железнодорожникам и строителям ускорить работу. Напишите программу, которая отсортирует вагоны в нужном порядке, склеивая их минимальное количество раз.

Исходные данные

В первой строке записано целое число N — количество вагонов в составе (1 ≤ N ≤ 10000). Во второй строке записано N чисел — начальный порядок вагонов. Все вагоны имеют различные номера от 1 до N. В результате сортировки вагоны должны быть выстроены по порядку, начиная с первого.

Результат

В первой строке выведите число K — минимальное количество склеиваний, которое необходимо, чтобы отсортировать вагоны. Далее выведите K + 1 строку, в каждой по N чисел через пробел. В первой строке выведите начальный порядок вагонов, в каждой следующей — порядок после очередного склеивания.

Примеры

исходные данныерезультат
5
5 1 3 2 4
2
5 1 3 2 4
1 2 5 3 4
1 2 3 4 5
6
6 5 2 4 1 3
3
6 5 2 4 1 3
6 4 1 5 2 3
6 1 2 3 4 5
1 2 3 4 5 6
Автор задачи: Сергей Пупырев
Источник задачи: XII Чемпионат УрГУ по программированию, 6 октября, 2007