数据结构上机实践课程(2018年秋)10月机考

C. 自然合并排序

单点时限: 5.0 sec

内存限制: 512 MB

自然合并排序是合并排序算法的一种改进, 对于初始给定的数组, 通常存在多个长度大于1的已自然排好序的子数组段。

例如, 若数组$a$中元素为$(1, 5, 2, 3, 6, 0, 7, 4, 8,9,10)$, 则自然排好序的子数组段有$((1, 5), (2, 3, 6), (0, 7), (4, 8),(9,10))$。

然后将相邻的排好序的子数组段两两合并,构成更大的排好序的子数组段$((1, 2, 3, 5, 6), (0, 4, 7, 8),(9,10))$。

继续合并相邻排好序的子数组段$((0,1,2,3,4,5,6,7,8),(9,10))$。

最后合并为$((0,1,2,3,4,5,6,7,8,9,10))$

输入格式

输入共两行

第一行一个整数$n(n\leqslant10^6)$表示数字序列的长度

第二行$n$个整数表示需要排序的序列

输出格式

每次将相邻的排好序的子数组段两两合并之后,输出一行整数,以空格分割,表示当前的序列顺序,直到排序结束。

样例

Input
10
67 77 82 74 83 23 58 58 93 86
Output
67 74 77 82 83 23 58 58 86 93
23 58 58 67 74 77 82 83 86 93
Input
10
21 39 58 69 98 64 28 84 78 57
Output
21 39 58 64 69 98 28 78 84 57
21 28 39 58 64 69 78 84 98 57
21 28 39 57 58 64 69 78 84 98

提示

当子数组的个数是奇数时,先不合并最后一个子数组。

仅在每轮合并过后输出,如果数组原来就是有序的,你不需要输出任何信息。