// sunt curios daca quicksort cu pivot random intra in timp la aceasta prb
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <time.h>

std::ifstream f("algsort.in");
std::ofstream g("algsort.out");

const int NMAX =  500005;
int n,v[NMAX];

int part(int *v,int left,int right){

    int random = left + (rand() + rand() - rand() ) % (right - left);
    std::swap(v[right],v[random]);

    int index = left;
    int pivot = v[right];

    for(int i = left;i < right;++i){
        if(v[i] <= pivot){
            std::swap(v[index],v[i]);
            index++;
        }
    }

    std::swap(v[index],v[right]);

    return index;
}

void quickSort(int *v,int left,int right){
    if(left < right){
        int index = part(v,left,right);
        quickSort(v,left,index - 1);
        quickSort(v,index + 1,right);
    }
}

int main(){

    srand(time(NULL));

    f >> n;

    for(int i = 1;i <= n;++i)
        f >> v[i];

    quickSort(v,1,n);

    for(int i = 1;i <= n;++i)
        g << v[i] << ' ';

    return 0;
}