#include <stdint.h>

#include <fstream>

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

using namespace std;

const uint32_t MAX_ITEMS = 500000;

uint32_t A[MAX_ITEMS];
uint32_t N;

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

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

    input.close();
}

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

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

    output.close();
}

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

    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(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;
}