#include<vector>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<iostream>
using namespace std;

void swap(int& a, int& b)
{
	int aux=a;
	a=b;
	b=aux;
}

int mid(const int& a, const int& b, const int& c)
{
	int mij;

	if(a>=b)
	{
		if(b>=c)
			mij=0;
		else
		{
			if(a<=c)
				mij=1;
			else
				mij=2;
		}
	}
	else
	{
		if(a>=c)
			mij=0;
		else
		{
			if(b<=c)
				mij=1;
			else
				mij=2;
		}
	}
	return mij;	
}

int partition(vector<int>& v, int left, int right)
{
	int len=right-left+1,x[3];
	x[0]=rand()%len;
	do
	{
		x[1]=rand()%len;
	}
	while(x[1]==x[0]);
	
	if(len>2)
	{
		do
		{
			x[2]=rand()%len;
		}
		while(x[2]==x[0] || x[2]==x[1]);
	}
	else
		x[2]=x[1];
	
	int index=x[mid(v[left+x[0]],v[left+x[1]],v[left+x[2]])];

	swap(v[left],v[left+index]);
	int pivot=v[left];
	int i=left+1,j;

	for(j=left+1;j<=right;++j)
	{
		if(v[j]>pivot)
			break;
		++i;
	}
	++j;	

	for(;j<=right;++j)
	{
		 if(v[j]<=pivot)
		 {
			swap(v[j],v[i]);
			++i;
		}
	}
	swap(v[i-1],v[left]);
	return i-1;
}

void quick_sort(vector<int>& v, int left, int right)
{
	if(left<right)
	{
		int r=partition(v,left,right);
		quick_sort(v,left,r-1);
		quick_sort(v,r+1,right);
	}
}
	
int main()
{
	ifstream in("algsort.in");
	ofstream out("algsort.out");
	int n;
	vector<int> v;
	in>>n;
	int nr;
	
	for(int i=0;i<n;++i)
	{
		in>>nr;
		v.push_back(nr);
	}
	srand(time(NULL));
	quick_sort(v,0,n-1);

	for(int i=0;i<n;++i)
		out<<v[i]<<" ";
	out<<"\n";
	in.close();
	out.close();
}