#include <vector>
#include <iostream>
#include <cstdlib>
//#include <gtest/gtest.h>

using std::vector;
using std::swap;

int partition2(vector<int> &a, int l, int r) {
	int x = a[l];
	int j = l;
	for (int i = l + 1; i <= r; i++) {
		if (a[i] <= x) {
			j++;
			swap(a[i], a[j]);
		}
	}
	swap(a[l], a[j]);
	return j;
}
vector<int> partition3(vector<int> &a, int l, int r) {
	int x = a[l];
	int j = l;
	int dupCount = 0;
	int biggerNumCount = 0;

	for (int i = l + 1; i <= r; i++) {
		if (a[i] < x) {
			int t = a[i];
			a[j] = t;
			t = a[i - biggerNumCount];
			a[i] = t;
			a[i - biggerNumCount] = x;
			j++;
			continue;
		}
		if (a[i] == x) {
			int t = a[j + dupCount + 1];
			a[i] = t;
			a[j + dupCount + 1] = x;
			dupCount++;
			continue;
		}
		biggerNumCount++;
	}
	vector<int> m = { j, j + dupCount };
	return m;
}

void randomized_quick_sort(vector<int> &a, int l, int r) {
	if (l >= r) {
		return;
	}

	int k = l + rand() % (r - l + 1);
	swap(a[l], a[k]);
//	int m = partition2(a, l, r);

	vector<int> m = partition3(a, l, r);

	randomized_quick_sort(a, l, m[0] - 1);
	randomized_quick_sort(a, m[1] + 1, r);
}

//TEST(ImprovedQuickSort, test1) {
//	vector<int> a = { 2, 3, 9, 2, 2 };
//	vector<int> result = { 2, 2, 2, 3, 9 };
//	randomized_quick_sort(a, 0, a.size() - 1);
//	ASSERT_EQ(result, a);
//}

int main() {
	int n;
	std::cin >> n;
	vector<int> a(n);
	for (size_t i = 0; i < a.size(); ++i) {
		std::cin >> a[i];
	}
	randomized_quick_sort(a, 0, a.size() - 1);
	for (size_t i = 0; i < a.size(); ++i) {
		std::cout << a[i] << ' ';
	}
}