#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void shellsort(int *v,int n) {
    int inc[] = {4095,2047,1023,255,127,63,31,15,7,3,1};
    int k = sizeof(inc) / sizeof(int);
    int i,j,l,y,m;
    for (y=0;y<k;y++) {
        //printf("%d ",inc[y]);
        for (i=0;i<=inc[y]-1;i++) {
            for (j=i+inc[y];j<n;j+=inc[y]) {
                m = v[j];
                l = j;
                while (l > i && v[l-inc[y]] > m) {
                    v[l] = v[l-inc[y]];
                    l -= inc[y];
                }
                v[l] = m;
            }
        }
    }
}

int main()
{
    int *v,n,i;
    //int x,j;
    FILE *f = fopen("algsort.in","r");
    fscanf(f,"%d",&n);
    v = (int*)malloc(n*sizeof(int));
    for (i=0;i<n;i++) fscanf(f,"%d",&v[i]);
    fclose(f);
    shellsort(v,n);
    /*for (i=1;i<n;i++) {
        x = v[i];
        j = i;
        while (j > 0 && v[j-1] > x) {
            v[j] = v[j-1];
            j--;
        }
        v[j] = x;
    }*/
    //for (i=0;i<n-1;i++) if (v[i] > v[i+1]) exit(1);
    f = fopen("algsort.out","w");
    for (i=0;i<n;i++) fprintf(f,"%d ",v[i]);
    //printf("%.2f",(float)clock()/CLOCKS_PER_SEC);
    fclose(f);
    return 0;
}