#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int v[500000];

void swap(int i, int j){
    int aux;
    aux=v[i];
    v[i]=v[j];
    v[j]=aux;
}

int partitie(int st, int dr){
    int i, j=st;
    for(i=st;i<dr;i++)
        if(v[i]<v[dr])
            swap(i, j++);
    swap(j, dr);

    return j;
}

void qs(int st, int dr){
    int p;
    if(st>=dr)
        return;
    p=partitie(st, dr);
    qs(st, p-1);
    qs(p+1, dr);
}

int main(){
    srand(time(0));
    FILE *fin, *fout;
    int n, i, j;
    fin=fopen("algsort.in", "r");
    fout=fopen("algsort.out", "w");
    fscanf(fin, "%d", &n);
    for(i=0;i<n;i++)
        fscanf(fin, "%d", &v[i]);
    for(i=n-1;i>=0;i--){
        j=rand()%(i+1);
        swap(i, j);
    }
    qs(0, n-1);
    for(i=0;i<n;i++)
        fprintf(fout, "%d ", v[i]);
    fclose(fin);
    fclose(fout);

    return 0;
}