//QuickSort
#include <cstdio>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#define NMAX 500003

using namespace std;

int v[NMAX],n;

int poz(int st, int dr)
{
    int i;
    int p = rand()%(dr-st) + st, is=st, id=dr, ip=0;
    for(i=1; i<=n; i++)
        if(v[i]<=v[p])ip++;
    swap(v[ip],v[p]);

    do
    {
        while(is<ip && v[is]<v[ip]) is++;
        while(id>ip && v[id]>v[ip]) id--;
        if(is<ip)
            swap(v[is++],v[id--]);
    }
    while(is<ip);
    return ip;
}

void quick(int s, int d)
{
    int m;
    if(s<d)
    {
        m = poz(s,d);
        quick(s,m-1);
        quick(m+1,d);
    }
}


int main()
{
    int i;
    FILE *f = fopen("algsort.in", "r");
    fscanf(f, "%d", &n);
    for(i=1; i<=n; i++)
        fscanf(f, "%d", &v[i]);
    fclose(f);

    srand(time(NULL));
    quick(1,n);

    f = fopen("algsort.out", "w");
    for(i=1; i<=n; i++)
        fprintf(f, "%d ", v[i]);
    fclose(f);
    return 0;
}