#include <fstream>
#include <algorithm>
#include <cstdlib>
using namespace std;

const int Nmax = 500005;
const int inf = (1LL << 31) - 1;

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

int n;
int v[Nmax];


/*
	Lomuto.
*/

void QuickSort1(int left, int right) {
	if (right <= left) return;

	int i = left - 1;
	int p = (rand() % (right - left + 1) + left);
	swap(v[p], v[right]);
	p = v[right];

	for (int j = left; j < right; ++j)
		if (v[j] < p) {
			++i;
			swap(v[i], v[j]);
		}
	swap(v[i + 1], v[right]);

	QuickSort1(left, i);
	QuickSort1(i + 2, right);
}


/*
	Lomuto.
	Instead of sending all elements equal to the pivot in one side,
	we divide them equally.
*/

void QuickSort2(int left, int right) {
	if (right <= left) return;

	int i = left - 1;
	int p = (rand() % (right - left + 1) + left);
	swap(v[p], v[right]);
	p = v[right];
	bool on_left = 0;

	for (int j = left; j < right; ++j)
		if (v[j] < p) {
			++i;
			swap(v[i], v[j]);
		}
		else if (v[j] == p) {
			if (on_left) {
				++i;
				swap(v[i], v[j]);
			}
			on_left ^= 1;
		}
	swap(v[i + 1], v[right]);

	QuickSort2(left, i);
	QuickSort2(i + 2, right);
}


/*
	Hoare. Classic. The sentinel is needed so that j doesn't go out of bound.
*/

void QuickSort3(int left, int right) {
	if (right <= left) return;

	int i = left - 1;
	int j = right;
	int p = (rand() % (right - left + 1) + left);
	swap(v[p], v[right]);
	p = v[right];

	while (i < j) {
		do ++i; while (v[i] < p);
		do --j; while (v[j] > p);
		if (i < j) swap(v[i], v[j]);
	}
	swap(v[i], v[right]);

	QuickSort3(left, i - 1);
	QuickSort3(i + 1, right);
}


/*
	Hoare.
	Version without sentinel. Instead of do_while use while_do
	and less than or equal checks (both while check and if check are
	necessary.
*/

void QuickSort4(int left, int right) {
	if (right <= left) return;

	int i = left;
	int j = right;
	int p = v[(rand() % (right - left + 1) + left)];

	while (i <= j) {
		while (v[i] < p) ++i;
		while (v[j] > p) --j;
		if (i <= j) {
			swap(v[i], v[j]);
			++i;
			--j;
		}
	}

	QuickSort4(left, i - 1);
	QuickSort4(i, right);
}

int main() {
	in >> n;
	for (int i = 1; i <= n; ++i)
		in >> v[i];

	// Sentinel is needed for QuickSort3
	v[0] = -inf;
	QuickSort2(1, n);

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

	return 0;
}