#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> pii;

pii partition(vector<int> &a, int l, int r)
{
	int sz = (r - l + 1);
	
	int m = l + rand() % sz;
	int item_m = a[m];
	
	int cnt_m = 0, cnt_l = 0, cnt_h = 0;
	
	for (int i = l; i <= r; i++)
		if (a[i] < item_m) cnt_l++; else
			if (a[i] > item_m) cnt_h++; else
				if (a[i] == item_m) cnt_m++;
	
	int x = l + cnt_l;
	
	for (int i = l; i <= r; i++)
	{
		if (i >= l + cnt_l && i <= r - cnt_h) continue;
		
		while (x <= r && a[x] == item_m) x++;
		
		if (x > r - cnt_h) break;
		
		if (a[i] == item_m) swap(a[i], a[x]);
	}
	
	x = l;
	int y = l + cnt_l + cnt_m;
	
	while (true)
	{
		while (x < l + cnt_l && a[x] < item_m) x++;
		
		while (y <= r && a[y] > item_m) y++;
		
		if (x >= l + cnt_l || y > r) break;
		
		swap(a[x], a[y]);
	}
	
	return { l + cnt_l, r - cnt_h };
}

void quicksort(vector<int> &a, int l, int r)
{
	if (l >= r) return;
	
	pii pivot = partition(a, l, r);
	
	quicksort(a, l, pivot.first - 1);
	quicksort(a, pivot.second + 1, r);
}

int main() 
{
	freopen("algsort.in", "r", stdin);
	freopen("algsort.out", "w", stdout);
	
	int n;
	cin >> n;
	
	vector <int> in(n);
	
	for (int i = 0; i < n; i++) cin >> in[i];
	
	quicksort(in, 0, (int)in.size() - 1);
	
	for (auto item: in) cout << item << ' ';
	
	return 0;
}