1539. [Ural 1568] 火车车厢排序

【题目描述】

在叶卡捷琳堡，有一些塔在同时被建造。建筑需要许多高质量的五金件和材料，它们中的大部分通过铁路运来。铁路运输并不总像承包商希望的那样快。火车在中间站停了太久，它们在那里被排好序并且定向到通向不同地区的铁轨。

正如你所知，货运列车车厢以如下方式被排序：火车被开到一个双向岔道，在那里每一节车厢都可以走左边或右边的岔道。之后，这些车厢重新连接起来。例如，如果车厢的顺序是“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之间独特的编号。这些车厢必须被重新排列使得编号递增，从1开始。

【输出格式】

输出文件的第一行有一个正整数K，即重新连接操作的最小次数。接下来的K+1行每行有N个正整数。在第一行输出车厢最初的顺序，接下来的每一行都输出一次重新连接后车厢的顺序。

【样例输入】

sample 1:

5

5 1 3 2 4

sample 2:

6

6 5 2 4 1 3

【样例输出】

sample 1:

2

5 1 3 2 4

1 2 5 3 4

1 2 3 4 5

sample 2:

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

【提示】

对于40%的数据，1<=N<=10

对于60%的数据，1<=N<=1000

对于100%的数据，1<=N<=10000

【来源】

Problem Author: Sergey Pupyrev

Problem Source: The XIIth USU Programing Championship, October 6, 2007

URAL 1568