#include <fstream>
#include <stdlib.h>
#include <ctime>
using namespace std;

ifstream fin ("algsort.in");
ofstream fout ("algsort.out");
int n,i,p,v[500002];
int poz (int st,int dr){
    int dst = 0;
    int ddr = -1;
    int aux;
    while (st < dr){
        if (v[st] > v[dr]){
            swap (v[st],v[dr]);
            aux = dst;
            dst = -ddr;
            ddr = -aux;
        }
        st += dst;
        dr += ddr;
    }
    return st;
}

void sorteaza (int st,int dr){
    if (st <= dr){
        int p = poz (st,dr);
        sorteaza (st,p-1);
        sorteaza (p+1,dr);

    }

}

int main (){

    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i];

    srand (time(0));
    /// functia rand returneaza un numar aleator intre 0 si 32000
    for (i=n-1;i>=3;i--){
        p = 1 + rand() % (i-1);
        swap (v[p],v[i]);
    }

    sorteaza (1,n);
    for (i=1;i<=n;i++)
        fout<<v[i]<<" ";


    return 0;
}