#include <fstream>
#include <stdlib.h>
#include <time.h>

using namespace std;

const char InFile[]="algsort.in";
const char OutFile[]="algsort.out";
const long int MaxN=500010;

long int N, v[MaxN];

long int random(long int start, long int finish){
	return ((rand()%(finish-start+1))+start);
}

long int partition(long int i, long int j){
	bool mod=true;
	long int aux, rand_pivot;
	long int pivot1=random(i,j);
	long int pivot2=random(i,j);
	long int pivot3=random(i,j);
	if(v[pivot1]<=v[pivot2] && v[pivot2]<=v[pivot3])
	{
		rand_pivot=pivot2;
	}
	else if(v[pivot2]<=v[pivot1] && v[pivot1]<=v[pivot3])
	{
		rand_pivot=pivot1;
	}
	else
	{
		rand_pivot=pivot3;
	}
	aux=v[i];
	v[i]=v[rand_pivot];
	v[rand_pivot]=aux;
	while(i<j){
		if(v[i]>v[j]){
			aux=v[i];
			v[i]=v[j];
			v[j]=aux;
			mod=!mod;
		}
		if(mod){
			--j;
		}else{
			++i;
		}
	}
	return i;
}

void qsort(long int start,long int end){
	if(start<end){
		long int pivot=partition(start,end);
		qsort(start,pivot-1);
		qsort(pivot+1,end);
	}
}

int main(){
	srand(time(NULL));
	
	ifstream fin(InFile);
	fin>>N;
	for(register int i=1;i<=N;++i){
		fin>>v[i];
	}
	fin.close();
	
	qsort(1,N);
	
	ofstream fout(OutFile);
	for(register int i=1;i<=N;++i){
		fout<<v[i]<<" ";
	}
	fout.close();
	return 0;
}