#include <bits/stdc++.h>

using namespace std;
const int nmax=10005;
vector<int> smaller,bigger;
int v[nmax];
int n,i;
void qs(int l,int r)
{
    if(l>=r) return;
    int poz=(rand()%(r-l+1));
    int val=v[poz+l];
    smaller.resize(0);
    bigger.resize(0);
    int eqcount=0;
    ///v[i]=*(v+i)=*(i+v)=i[v]
    for(int i=l;i<=r;i++)
    {
        if(i[v]<val) smaller.push_back(v[i]);
        if(i[v]>val) bigger.push_back(v[i]);
        if(i[v]==val) eqcount+=1;
    }
    int wh=l;
    for(auto small:smaller)
        v[wh++]=small;
    for(int i=1;i<=eqcount;i++)
        v[wh++]=val;
    for(auto big:bigger)
        v[wh++]=big;
    int sm=smaller.size(),bg=bigger.size();
    qs(l,l+sm-1);
    qs(r-bg+1,r);
}
int main()
{
    ifstream f("algsort.in");
    ofstream g("algsort.out");
    srand(time(NULL));
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    qs(1,n);
    for(i=1;i<=n;i++)
        g<<v[i]<<' ';
    return 0;
}