#include <fstream.h>
#include <time.h>
#include <stdlib.h>
#define MAX 500002

ifstream f("algsort.in");
ofstream g("algsort.out");

int v[MAX],s[2000];

//void quicksort(int start,int stop);

int main()
{
	int i,j,p,n,aux,c=0,start,stop;
	
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	
	srand (time(NULL));
	
	s[c++]=1;
	s[c++]=n;
	while(c>0)
	{
		stop=s[--c], start=s[--c];
		if(stop<=start)
			continue;
		
		i=start;
		j=stop;
		p=v[(start+stop)>>1];
		while(i<j)
		{
			while(v[i]<p && i<=stop)
				i++;
			while(v[j]>p && j>=start)
				j--;
			if(i<j)
			{
				aux=v[i], v[i]=v[j], v[j]=aux;
				if(v[i]==v[j]) j--;
			}
			
		}
		
			if(i-start > stop-i)
			{
				s[c++]=i, s[c++]=stop;
				s[c++]=start, s[c++]=i-1;
			}
			else
			{
				s[c++]=i+1, s[c++]=stop;
				s[c++]=start, s[c++]=i;
			}
		
	}
	
	for(i=1;i<=n;i++)
		g<<v[i]<<" ";
	
	f.close();
	g.close();
	return 0;
}

/** QUICKSORT RECURSIV **/
/*void quicksort(int start, int stop)
{
	int i,p,j,aux;
	
	if(stop-start<1) return;
	i=start;
	j=stop;
	p=v[(i+j)/2];
	while(i<j)
	{
		while(v[i]<p)
			i++;
		while(v[j]>p)
			j--;
		if(i<j)
		{
			aux=v[i], v[i]=v[j], v[j]=aux;
			if(v[i]==v[j]) j--;
		}
		
	}
	
	quicksort(start,i);
	quicksort(i+1,stop);
}*/