#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXN 500000
#define LGBUBSORT 10

void readData(int *n, int *v)
{
    int i;
    scanf("%d",n);
    for(i = 1; i <= *n; i++)
        scanf("%d",&v[i]);
}

void printVector(int n, int *v)
{
    int i;
    for(i = 1; i <= n; i++)
        printf("%d ",v[i]);
}

void swap(int *x, int *y)
{
    int aux = *x;
    *x = *y;
    *y = aux;
}

void shuffleArray(int n, int *v)
{
    int i;
    for(i = n; i >= 2; i--)
    {
        int p = rand()%(i-1) + 1;
        swap(&v[p],&v[i]);
    }
}

void bubbleSort(int lo, int hi, int *v)
{
    int sortat,i;

    do
    {
        sortat = 1;

        for(i = lo; i < hi; i++)
            if(v[ i ] > v[i + 1])
            {
                swap(&v[i],&v[i+1]);
                sortat = 0;
            }
    }
    while(sortat == 0);
}

int medianOf3(int i, int j, int k, int *v)
{
    int a = v[ i ], b = v[ j ], c = v[ k ];

    if(b < a)
    {
        swap(&b,&a);
        swap(&i,&j);
    }

    if(c < a)
    {
        swap(&c,&a);
        swap(&i,&k);
    }

    if(b > c)
    {
        swap(&b,&c);
        swap(&j,&k);
    }

    return j;
}



int partition(int lo, int hi, int *v)
{
    int i = lo + 1, j = hi, p;

    //p = lo + rand()%(hi-lo+1);
    p = medianOf3(lo,lo + (hi-lo)/2,hi,v);

    swap(&v[p],&v[lo]);

    while(1)
    {
        for( ; v[ i ] <= v[lo] && i <= hi; i++);

        for( ; v[ j ] >= v[lo] && j >= lo + 1; j--);

        if(i > hi) break;

        if(j <= lo) break;

        if(i >= j) break;

        swap(&v[i],&v[j]);
    }

    swap(&v[j],&v[lo]);

    return j;
}

void sort(int lo, int hi, int *v)
{
     if(hi - lo + 1 <= LGBUBSORT)
     {
        bubbleSort(lo,hi,v);
        return;
    }

    if(lo > hi)
        return;

    int pos = partition(lo,hi,v);
    sort(lo,pos-1,v);
    sort(pos+1,hi,v);
}


void sort2(int lo, int hi, int *v)
{
    //int p = medianOf3(lo,lo + (hi-lo)/2,hi,v);
    int p = lo + rand()%(hi-lo+1);
    swap(&v[p],&v[lo]);

    int lt = lo, i = lo + 1, gt = hi, ref = v[lo];

    while(i <= gt)
    {
        if(v[ i ] < ref)
        {
            swap(&v[i],&v[lt]);
            i++;
            lt++;
        }
        else
        {
            if(v[ i ] == ref)
                i++;
            else
            {
                swap(&v[ i ], &v[ gt ]);
                gt--;
            }
        }
    }

    sort(lo,lt-1,v);
    sort(lt+1,hi,v);
}

int main()
{
    freopen("algsort.in","r",stdin);
    freopen("algsort.out","w",stdout);

    int n, v[MAXN+1];

    readData(&n,v);

    srand(time(NULL));

   // shuffleArray(n,v);

    sort2(1,n,v);

    printVector(n,v);

    return 0;
}