#include <fstream>
#include <iostream>
#include <cstdlib>
#include <cassert>

using namespace std;
const int N=500005;
int v[N],n;
void citeste()
{
    int i;
    ifstream fin("algsort.in");
    fin>>n;
    for(i=1; i<=n; i++)
        fin>>v[i];
}
void scrie()
{
    int i;
    ofstream fout("algsort.out");
    for(i=1; i<=n; i++)
        fout<<v[i]<<' ';
    fout<<'\n';
}
int s[N], d[N];
int poz(int i, int j)
{
    int x=v[i],k=0,l=0,q=i;
    for(int poz=i+1; poz<=j; poz++)
    {
        if(v[poz]<=v[i])
            s[++k]=v[poz];
        else
            d[++l]=v[poz];
    }
    for(int poz=1; poz<=k; poz++)
        v[q++]=s[poz];
    v[q++]=x;
    for(int poz=1; poz<=l; poz++)
        v[q++]=d[poz];
    return i+k;
}
int poz_piv(int i,int j,int piv)
{
    int cnt=0;
    for(int poz=i;poz<=j;poz++)
     cnt+=v[poz]<v[piv];
    return i+cnt;
}
void sortare(int i, int j)
{
    if(i<=j)
    {
        ///int k=poz(i,j);

        int dist = j-i+1;
        int p1 = poz_piv(i, j, i + rand() % dist);
        int p2 = poz_piv(i, j, i + rand() % dist);
        int p3 = poz_piv(i, j, i + rand() % dist);

        int mij = (i+j)/2;
        int d1 = abs(p1 - mij);
        int d2 = abs(p2 - mij);
        int d3 = abs(p3 - mij);

        int min_p = p1;
        int min_d = d1;
        if(d2 < min_d) min_p = p2, min_d = d2;
        if(d3 < min_d) min_p = p3, min_d = d3;

        swap(v[i], v[min_p]);
        assert(i <= min_p);
        assert(min_p <= j);
        int k = poz(i, j);
        sortare(i,k-1);
        sortare(k+1,j);
    }
}


int main()
{
    citeste();
    sortare(1,n);
    scrie();
    return 0;
}