#include <fstream>
#include <time.h>

using namespace std;

inline void Interschimba(int &a, int &b){
	int c;

	c = a;
	a = b;
	b = c;
}

int Partition(int *a, int p, int r){
	
	int i, x;
	x = a[r];
	i = p - 1;

	for (int j = p; j <= r - 1; j++)
		if (a[j] <= x){
			i++;
			Interschimba(a[i], a[j]);
		}

	Interschimba(a[i + 1], a[r]);
	return i + 1;
}

int RandomizedPartition(int *a, int p, int r){

	int i;
	srand(time(NULL));

	i = rand() % r + p;
	Interschimba(a[r], a[i]);

	return Partition(a, p, r);

}

void QuickSort(int *a, int p, int r){

	int q;

	if (p < r){
		q = RandomizedPartition(a, p, r);
		QuickSort(a, p, q - 1);
		QuickSort(a, q + 1, r);
	}
}

int main(){

	ifstream in("algsort.in");
	ofstream out("algsort.out");

	const int NMAX = 500005;
	int n, *a = new int[NMAX];

	in >> n;

	for (int i = 1; i <= n; i++)
		in >> a[i];

	QuickSort(a, 1, n);

	for (int i = 1; i <= n; i++)
		out << a[i] << " ";

	return 0;
}