#include <fstream>
#include <cstdlib>
#include <algorithm>
#include <ctime>
using namespace std;

const int N = 1 + 5e5, gap[] = {16, 1, 4, 9, 20, 46, 103, 233, 525, 1182, 2660, 5985, 13467, 30301, 68178, 153401, 345152};

int v[N];

void qsort(int st, int dr){
    if (dr <= st)
        return;

    swap( v[dr], v[st + rand() % (dr - st + 1)] );
    int poz = st;
    for (int i = st ; i < dr ; i++)
        if ( v[i] <= v[dr] ){
            swap(v[i], v[poz]);
            poz++;
        }

    int dvd = st;
    for (int i = st ; i < poz ; i++)
        if (v[i] < v[dr]){
            swap(v[i], v[dvd]);
            dvd++;
        }
    swap(v[poz], v[dr]);

    qsort(st, dvd - 1);
    qsort(poz + 1, dr);
}

void shellSort(int st, int dr){
    bool flag;
    for (int k = gap[0] ; k ; k--){
        flag = true;
        while (flag){
            flag = false;
            for (int i = st, j = st + gap[k] ; j <= dr ; i++, j++)
                if ( v[i] > v[j] ){
                    swap(v[i], v[j]);
                    flag = true;
                }
        }
    }
}

int main(){
    ifstream in("algsort.in");
    for (int i = 0 ; i <= v[0] ; i++)
        in >> v[i];
    in.close();

    srand( time(NULL) );
    qsort(1, v[0]);
    //sort(v + 1, v + v[0] + 1);

    ofstream out("algsort.out");
    for (int i = 1 ; i <= v[0] ; i++)
        out << v[i] << ' ';
    out << '\n';
    out.close();

    return 0;
}