#include <fstream>
#include<time.h>
#include<stdlib.h>
#define NMAX 500000
using namespace std;
int v[NMAX];
int AlegePivot(int st,int dr)
{
    int a=st+rand()%(dr-st+1);
    int b=st+rand()%(dr-st+1);
    int c=st+rand()%(dr-st+1);
    if(v[a]>v[b])
    {
        if(v[b]>=v[c]) return b;
        if(v[c]<=v[a]) return c;
        return a;
    }
    if(v[a]==v[b]) return a;
    if(v[c]<=v[a]) return a;
    if(v[c]<=v[b]) return c;
    return b;
}
int Partitioneaza(int st,int dr,int ValPivot)
{
    int i=st-1,j=dr+1;
    while(1)
    {
        do
        {
            ++i;
        }
        while(v[i]<ValPivot);
        do
        {
            --j;
        }
        while(v[j]>ValPivot);
        if(i>=j) return j;
        v[j]^=v[i]^=v[j]^=v[i];
    }
}
void quicksort(int st,int dr)
{
    if(st<dr)
    {
        int pivot=AlegePivot(st,dr);
        pivot=Partitioneaza(st,dr,v[pivot]);
        quicksort(st,pivot);
        quicksort(pivot+1,dr);
    }
}
int main()
{
    srand(time(NULL));
    ifstream f("algsort.in");
    ofstream g("algsort.out");
    int n,i;
    f>>n;
    for(i=0; i<n; ++i) f>>v[i];
    quicksort(0,n-1);
    for(i=0; i<n; ++i) g<<v[i]<<' ';
    return 0;
}