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

FILE *fin, *fout;

int a[500000];

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

void partition(int v[], int st, int dr, int *p1, int *p2) {
    int poz = rand() % (dr - st + 1) + st;
    swap(&v[poz], &v[dr]);
    *p1 = st;
    *p2 = dr - 1;
    int i = st;
    while(i <= *p2) {
        if(v[i] == v[dr])
            ++i;
        else if(v[i] < v[dr])
            swap(&v[(*p1)++], &v[i++]);
        else
            swap(&v[(*p2)--], &v[i]);
    }
    swap(&v[++(*p2)], &v[dr]);
}

void quicksort(int v[], int st, int dr) {
    if(st >= dr)
        return;
    int p1, p2;
    partition(v, st, dr, &p1, &p2);
    quicksort(v, st, p1-1);
    quicksort(v, p2+1, dr);
}

int main(void) {
    srand(1234567);
    fin = fopen("algsort.in", "r");
    int n;
    fscanf(fin, "%d", &n);
    for(int i = 0; i < n; ++i) {
        fscanf(fin, "%d", &a[i]);
    }
    fclose(fin);
    quicksort(a, 0, n-1);
    fout = fopen("algsort.out", "w");
    for(int i = 0; i < n; ++i) {
        fprintf(fout, "%d ", a[i]);
    }
    fprintf(fout, "\n");
    fclose(fout);

    return 0;
}