#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

#define N 500001


int a[N];
int n;

inline int threeInTheMiddle(int l, int r)
{
	int x[5];
	int i;
	for (i = 0; i < 5; ++i)
		x[i] = l + rand () % (r - l + 1);
	sort (x, x + 5);
	return x[2];
}

int partitie(int a[], int l, int r)
{
	int i, nr = l;
	int p = threeInTheMiddle(l, r);
	swap (a[p], a[r]);
	for (i = l; i <= r; ++i)
		if (a[i] <= a[r])
			swap (a[nr++], a[i]);
	return nr - 1;
}

void quickSort(int a[], int l, int r)
{
	//printf ("%d %d\n", l,r);
	if (l >= r)
		return;
	int m = partitie(a, l, r);
	quickSort (a, l, m - 1);
	quickSort (a, m, r);
}

int main ()
{
	srand (time(0));
	freopen ("algsort.in", "r", stdin);
	freopen ("algsort.out", "w", stdout);
	scanf ("%d\n", &n);
	int i;
	for (i = 1; i <= n; ++i)
		scanf ("%d", &a[i]);

	quickSort(a, 1, n);

	for (i = 1; i <= n; ++i)
		printf ("%d ", a[i]);

	return 0;
}