#include <iostream>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("algsort.in");
ofstream g("algsort.out");

int i, n, v[500005];

void abracadabra(int st, int dr)
{
    if(st>=dr)
        return;
    int m=(rand()%dr-st+1)+st;
    for(int i=st; i<=dr; i++)
    {
        if(v[m]<v[i]&&m>i)
        {
            swap(v[m], v[i]);
            m=i;
        }
        if(v[m]>v[i]&&m<i)
        {
            swap(v[m], v[i]);
            m++;
            swap(v[m], v[i]);
        }
    }
    abracadabra(m+1, dr);
    abracadabra(st, m);
}


int main()
{
    f>>n;
    for(i=1; i<=n; i++)
    {
        f>>v[i];
    }
    srand(time(NULL));
    abracadabra(1, n);
    ///sort(v+1, v+n+1);
    for(i=1; i<=n; i++)
    {
        g<<v[i]<<' ';
    }
    return 0;
}