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

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

long long quick_sort(int a[600001] , int n);
long long partition(int a[600001] , int left , int right);

long long quick_sort(int a[600001] ,int  n)
{
	return partition(a,0,n-1);
}



long long partition(int a[600001] , int left , int right)
{
	if(right > left ){
		long long aa,b,c;
		
		/* choose pivot */
		int p = a[left] , i = left , m = (right-left+1)/2 + left;
		//swap(a[right],a[left]);
		aa = right - left;
		if(aa%2 == 1)
			m--;
		
		
		int l=left , r=right;
		if( ( a[l] > a[r] && a[r] > a[m] ) ||  ( a[m] > a[r] && a[r] > a[l] ) )
			p=r;
		if( ( a[l] > a[m] && a[m] > a[r] ) ||  ( a[r] > a[m] && a[m] > a[l] ) )
			p=m;
		if( ( a[r] > a[l] && a[l] > a[m] ) ||  ( a[m] > a[l] && a[l] > a[r] ) )
			p=l;
			
		if(p != left)
			swap(a[p],a[left]);
		p = a[left];
		
		/* partitioning */
		for(int j=left;j<=right;j++){
			if(a[j] < p){
				swap(a[++i],a[j]);
			}
		}
		swap(a[left],a[i]);
		
		/* recursion */
		b = partition(a,left,i-1);
		c = partition(a,i+1,right);
		
		/* total number of comparations*/
		return aa+b+c;
	}else
		return 0;

	
}



int main()
{
	int n , i=0;
	int a[600001];
	in>>n;
	for(i=0;i<n;i++)
		in>>a[i];
	
	quick_sort(a,i);

	for(int j=0;j<i;j++)
		out<<a[j]<<" ";
	
	return 0;
}