#include <iostream>
#include <fstream>
using namespace std;
ifstream in("algsort.in");
ofstream out("algsort.out");
int v[500001];
int n;
int pozitie(int poz,int mij)
{
    while(v[poz]<=v[mij] && poz<mij)
        poz++;
    return poz;
}
void sortare(int st, int dr)
{
    int mij=(st+dr)/2;
    int nr=0;
    for(int i=st;i<=dr;i++)
        if(v[i]<v[mij])
            nr++;
    swap(v[nr+1],v[mij]);
    int poz=nr+1;
    int i=1;
    nr=0;
    for(int i=nr+2;i<=dr;i++)
    {
        if(v[i]<v[nr+1])
        {
            poz=pozitie(poz,nr+1);
            swap(v[i],v[poz]);
        }
    }
    if(mij>=2)
        sortare(st,v[mij-1]);
    if(mij<n-1)
        sortare(v[mij+1],dr);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    sortare(1,n);
    for(int i=1;i<=n;i++)
        cout<<v[i]<<" ";
    return 0;
}