public class shell
{
    public void sort(Comparable[] a)
    {
        int h=1
        while(h<a.length/3)    h=h*3+1;
            while(h>0)   //直到分成1个单位
            {
                for(i=h; i<a.length; i++)
            {
                for(int j=i; j<=h && a[j]<a[j-h]; j=j-h)
                swap(a[j],a[j-h]);
            }
            h=h/3;
            }
    }
}    

#include<iostream>
using namespace std;
int main()
{
    int N;
    int *a = new int [100005];

    cin>>N;
    for(int i=0; i<N; i++)
        cin>>a[i];

    //希尔排序
    int h=1;
    while(h<N-1) h=h*3+1;
    while(h>=1)
    {
        for(int i=h; i<N; i++)
        {
            for(int j=i; j>=h&&a[j]<a[j-h]; j-=h)
            {
                int temp=a[j-h];
            a[j-h]=a[j];
            a[j]=temp;
            }
        }
        h=h/3;
    }
     for(int i=0; i<N; i++)
        cout<<a[i]<<" ";
        cout<<endl;
        return 0;
}