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

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

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

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;
	int num2 = 0;
	for (long i = in1; i <= in2; ++i) {
		if (a[i] < a[poz]) {
			++num;
		}
		else if( a[i ] == a[poz]) num2++;
	}
	
	swap(poz, in1 + num);
	int t = a[ in1 + num];
	in4 = in1 + num + 1;
	int in5 = in2;
	
	for (long i = in1; i <= in1 + num - 1; ++i) {
		while (a[i] >= t ) {
			if( a[ i ] > t)	{
				a[ i ] = a[ in5] ^ a[ i ] ^( a[ in5 ] = a [ i ] );
				in5--;
			}
			if( a[ i ] == t) {
				a[ i ] = a[ in4] ^ a[ i ] ^( a[ in4 ] = a [ 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]);
	}
	
	/*for( int i = n; i> 1; i--){
		printf("%ld ", a[i]);
	}
	printf("%d\n",a[1]);*/
	rec(1, n);
	
	for (i = 1; i < n; ++i) {
		printf("%ld ", a[i]);
	}
	printf("%ld\n",a[n]);
	return 0;
}