#include <fstream.h>
#include <iostream.h>
#define MAX 500001
#define MAXX 2000
ifstream f("algsort.in");
ofstream g("algsort.out");
int v[MAX],s[MAXX];
int partition(int a, int b);

int main()
{
	int i,n,c=0,stop,start,j,p,aux,k,end;
	
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];

	s[c++]=1;
	s[c++]=n;
	while(c>0)
	{
		stop=s[--c], start=s[--c];

		if(start>=stop)
			continue; 
		
		i=partition(start, stop);
		
		if(i-start > stop-i)
		{
				s[c++]=i+1, s[c++]=stop;
				s[c++]=start, s[c++]=i-1;
		}
		else
		{
			s[c++]=i+1, s[c++]=stop;
			s[c++]=start, s[c++]=i-1;
		}
	}
	
	for(i=1;i<=n;i++)
		g<<v[i]<<" ";
	
	f.close();
	g.close();
	return 0;
}

int partition(int start, int stop)
{
	int i=start, j=stop, p=v[(start+stop)/2],aux;
	
	if(stop<=start) return start;
	
	while(true)
	{
		while(v[i]<p)
			i++;
		while(v[j]>p)
			j--;
		if(i>=j) break;
		aux=v[i], v[i]=v[j], v[j]=aux;
		i++, j--;
	}
	//aux=v[i], v[i]=p, v[start]=aux;
	return i;
}