#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){

	srand(time(NULL));

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

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