#include <iostream>
#include <fstream>
#include <ctime>
#include <stdlib.h>
using namespace std;
ifstream in ("algsort.in");
ofstream out ("algsort.out");
int v[500001], N;
int med(int a, int b)
{
    int x, y, z;
    srand(time(NULL));
    x=a+rand()%(b-a+1);
    y=a+rand()%(b-a+1);
    z=a+rand()%(b-a+1);
    int e=max(min(v[x],v[y]), min(max(v[x],v[y]),v[z]));
    if (e==v[x])
        return x;
    if (e==v[y])
        return y;
    return z;

}
int part(int a, int b)
{
    int poz_piv=med(a,b);
    int piv=v[poz_piv];
    swap(v[poz_piv], v[b]);
    poz_piv=b;
    int i=a-1;
    for(int j=a;j<b;j++)
    {
        if(v[j]<=piv)
        {
            i++;
            swap(v[i], v[j]);
        }
    }
    i++;
    swap(v[i], v[poz_piv]);
    return i;
}

void quicksort(int a, int b)
{
    if(a<b)
    {
        int mid=part(a, b);
        quicksort(a, mid-1);
        quicksort(mid+1, b);
    }
}

int main()
{
    in>>N;
    for (int i=0;i<N;i++)
        in>>v[i];
    quicksort(0, N-1);
    for (int i=0;i<N;i++)
        out<<v[i]<<" ";
}