#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NMAX 500005
int n,A[NMAX],B[NMAX],r,t,p;
void read()
{
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
		scanf("%d",&A[i]);
}
void sorteaza(int st,int dr)
{
	if (st==dr || st>dr)
		return ;
	int i,poz=rand()%(dr-st+1)+st,val,l,salv;
	val=A[poz];
	r=t=0; p=st-1; l=dr-st+1;
	for (i=st; i<=dr; i++)
		if (A[i]<A[poz])
			B[++r]=A[i];
	for (i=st; i<=dr; i++)
		if (A[i]>A[poz])
		{
			t++;
			B[r+t]=A[i];
		}
	for (i=1; i<=r; i++)
		A[++p]=B[i];
	for (i=1; i<=l-r-t; i++)
		A[++p]=val;
	for (i=r+1; i<=r+t; i++)
		A[++p]=B[i];
	salv=t;
	sorteaza(st,st+r-1);
	sorteaza(dr-salv+1,dr);
}
void show()
{
	int i;
	for (i=1; i<=n; i++)
		printf("%d ",A[i]);
	printf("\n");
}
int main()
{
	freopen("algsort.in","r",stdin);
	freopen("algsort.out","w",stdout);
	read();
	srand(time(0));
	sorteaza(1,n);
	show();
	return 0;
}