#include<fstream>
#include<time.h>
#include<stdlib.h>
using namespace std;

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

int a[500001],n,pz,aux,i,j,ii,jj;

int poz(int ls , int ld)
{
	
	int pz = ls + rand()%(ld-ls+1);
	
	int aux = a[pz];
	a[pz]=a[ls];
	a[ls]=aux;
	
	i=ls;
	j=ld;
	ii=0,jj=-1;
	while(i!=j)
	{
		if(a[i]>a[j]){
			aux =a[i];
			a[i]=a[j];
			a[j]=aux;
			aux=ii;
			ii=-jj;
			jj=-aux;
		}
		i+=ii;
		j+=jj;
	}
	return i;
}

void sort(int ls,int ld){
	if(ls<ld){
		int p=poz(ls,ld);
		sort(ls,p-1);
		sort(p+1,ld);
	}
}

int main(){
	srand(time(0));
	int i;
	f>>n;
	for(i=1;i<=n;i++)
		f>>a[i];
	for(i=n;i>=3;i--)
	{
		pz=1+rand()%(i-1);
		aux=a[n];
		a[n]=a[pz];
		a[pz]=aux;
		
	}
	sort(1 , n );
	for(i=1;i<=n;i++)
		g<<a[i]<<" ";
	
	return 0;
}