#include <bits/stdc++.h>

using namespace std;

#define MAXSIZE 200000

typedef int KeyType;

typedef struct {

    KeyType key;

}RedType;

typedef struct {

    RedType r[MAXSIZE + ];

    int length;

}SqList;

int Random(int start, int end){

    int dis = end - start;

    return rand() % dis + start;

}

void ShellInsert(SqList &L,int dk) {

    int i, j;

    for (i = dk + ; i <= L.length; ++i)

        if(L.r[i].key < L.r[i - dk].key) {

            L.r[] = L.r[i];

            for (j = i - dk; j >  && L.r[].key < L.r[j].key; j -= dk)

                L.r[j + dk] = L.r[j];

            L.r[j + dk] = L.r[];

        }

}

void ShellSort (SqList &L, int dt[], int t) {

    double start_time, finish_time, cord_time;

    start_time = clock();

    int k;

    for (k = ; k < t; ++k) {

        ShellInsert(L, dt[k]);

    }

    finish_time = clock();

    cord_time = (double)(finish_time - start_time) ;

    printf("ShellSort time=%f ms\n", cord_time);

    // int i;

    // for (i = 0; i < 3; ++i)

    //     printf("%d\n",dt[i]);

}

// void Zengliang(SqList &L, int dt[]) {

//     for (int i = 1; i <=L.length; ++i) {

//         dt[i-1] = pow(2, i) - 1;

//     }

// }

void InPut(SqList &L) {

    int i;

    srand((unsigned)time(NULL));

    cin >> L.length;

    for (i = ; i <= L.length; ++i) {

        // cin >> L.r[i].key;

        L.r[i].key = Random(, );

    }

}

void OutPut(SqList &L) {

    int i;

    for (i = ; i <= L.length; ++i) {

        cout << L.r[i].key << " ";

    }

}

// void test (SqList &L, int dt[]) {

//     int i;

//     for (i = 0; i < L.length; ++i)

//         printf("%d\n",dt[i]);

// }

int main() {

    int dt[] = {, , };

    SqList L;

    // L.r = new RedType [MAXSIZE+1];

    InPut(L);

    // Zengliang(L, dt);

    // test(L, dt);

    ShellSort(L, dt, );

    OutPut(L);

    return ;

}