#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long a[500010], n, k, i;

void swap(long p1, long p2) {
	long m = a[p1];
	a[p1] = a[p2];
	a[p2] = m;
}

void rec(long in1, long in2) {
	if (in1 == in2) return;
	if (in1 + 1 == in2) {
		if (a[in1] > a[in2]) {
			swap(in1, in2);
		}
		return;
	}
	
	long poz = rand() % (in2 - in1 + 1) + in1, num = 0, in4 = 0;
	
	for (long i = in1; i <= in2; ++i) {
		if (a[i] < a[poz]) {
			++num;
		}
	}
	
	swap(poz, in1 + num);
	in4 = in1 + num + 1;
	
	for (long i = in1; i <= in1 + num - 1; ++i) {
		while (a[i] > a[in1 + num]) {
			swap(i, in4++);
		}
	}
	
	rec(in1, in1 + num);
	rec(in1 + num + 1, in2);
	
}

int main() {
	srand(100);
	freopen("algsort.in", "r", stdin);
	freopen("algsort.out", "w", stdout);
	scanf("%ld", &n);
	
	for (i = 1; i <= n; ++i) {
		scanf("%ld", &a[i]);
	}
	
	rec(1, n);
	
	for (i = 1; i <= n; ++i) {
		printf("%ld ", a[i]);
	}
	return 0;
}