题目描述

1959年Shell发明，第一个突破O(n​^2^​)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

1.选择一个增量序列$t_1，t_2，…，t_k，其中ti>tj，t_k=1；$

2.按增量序列个数k，对序列进行k 趟排序；

3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，

4.分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

输入

输入共两行，第一行包含整数 n。

第二行包含 n个整数（所有整数均在 1∼10^9^范围内），表示整个数列。

输出

输出共一行，包含 n个整数，表示排好序的数列。

5
3 1 2 4 5

1 2 3 4 5

提示

1≤n≤100000