#include <stdint.h>
#include <stdlib.h>     /* srand, rand */
#include <time.h>       /* time */

#include <fstream>
#include <algorithm>

using namespace std;

const uint32_t MAX_ELEMENTS = 500010;
uint32_t A[MAX_ELEMENTS];
uint32_t N;

void read(){
    ifstream in("algsort.in");

    in>>N;

    for(uint32_t i=1; i<=N; i++){
        in>>A[i];
    }

    in.close();
}

void write(){
    ofstream out("algsort.out");

    for(uint32_t i=1; i<=N; i++){
        out<<A[i]<<" ";
    }

    out.close();
}

uint32_t partition(uint32_t p, uint32_t r){
    uint32_t aux;
    uint32_t i = p - 1;
    uint32_t position = p + (rand() % (int)(r - p + 1));

    aux = A[r];
    A[r] = A[position];
    A[position] = aux;

    uint32_t x = A[r];
    for (uint32_t j = p; j< r; j++){
        if (A[j] <= x){
            i++;
            uint32_t aux = A[i];
            A[i] = A[j];
            A[j] = aux;
        }
    }

    i++;
    A[r] = A[i];
    A[i] = x;

    return i;
}

void quicksort(uint32_t p, uint32_t r){
    if(r-p<10){
        sort(A+p, A+r);
    }else{
        if (p<r){
            uint32_t q = partition(p, r);
            quicksort(p, q - 1);
            quicksort(q + 1, r);
        }
    }
}

void sortData(){
    quicksort(1, N);
}

int main()
{
    /* initialize random seed: */
    srand(time(NULL));

    read();
    sortData();
    write();

    return 0;
}