В Екатеринбурге строится сразу несколько небоскрёбов. Для их возведения требуется много стройматериалов высокого качества, большинство из которых доставляется в город по железной дороге. И эта доставка не всегда происходит так быстро, как этого хотели бы подрядчики. Все дело в том, что составы слишком долго простаивают на узловых станциях, пока их сортируют для отправки в разные концы страны.

Как известно, товарные вагоны сортируются следующим образом: состав подгоняется к развилке, где каждый вагон может проследовать по левому или правому пути. После этого состав «склеивается». Например, если вагоны были в порядке «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 чисел через пробел. В первой строке выведите начальный порядок вагонов, в каждой следующей — порядок после очередного склеивания.