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

void swap(int& a, int& b)
{
	if(&a!=&b)
	{
		a^=b;
		b^=a;
		a^=b;
	}
}

int ismid(const int& a, const int& b, const int& c)
{
	if(a>=b && a<=c)
		return 1;
	if(a>=c && a<=b)
		return 1;
	return 0;
}

int partition(vector<int>& v, int left, int right)
{
	int len=right-left+1;
	int index1=rand()%len;
	int index2=rand()%len;
	int index3=rand()%len;
	int index;

	if(ismid(v[index1],v[index2],v[index3]))
		index=index1;
	else if(ismid(v[index2],v[index1],v[index3]))
		index=index2;
	else
		index=index3;
	
	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();
}