#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

void quickSort(int v[], int start, int end){
    if(start >= end){
        return;
    }
    srand(rand());
    // int indPivot = start + (rand() % (end - start + 1));
    int indPivot = end;
    int pivot = v[indPivot];
    int lastSmaller, ind, aux;
    lastSmaller = start - 1;
    for(ind = start; ind <= end; ind++){
        if(v[ind] < pivot){
            lastSmaller++;

            aux = v[lastSmaller];
            v[lastSmaller] = v[ind];
            v[ind] = aux;
            if((lastSmaller == indPivot) || (ind == indPivot)){
                indPivot = ind;
            }
        }
    }
    
    aux = v[lastSmaller + 1];
    v[lastSmaller + 1] = pivot;
    v[indPivot] = aux;

    quickSort(v, start, indPivot - 1);
    quickSort(v, indPivot + 1, end);
}

int main(){
    ifstream in("algsort.in");
    ofstream out("algsort.out");
    int v[500000], n;
    in>>n;
    for(int i = 0; i < n; i++){
        in>>v[i];
    }
    quickSort(v, 0, n - 1);
    for(int i = 0; i < n; i++){
        out<<v[i]<<' ';
    }
    in.close();
}