#include <fstream>
#include <iostream>
#define nmax 500010
using namespace std;

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

int n;
int v[nmax];

void merge(int start, int mediu, int end){
	int contor1, contor2;
	int aux[end-start+2];
	int poz=0;
	for (contor1=start,contor2=mediu+1;contor1<=mediu || contor2<=end;)
	{
		if(contor1<=mediu&&contor2<=end) 
			if (v[contor1]<v[contor2]) 
				aux[poz++]=v[contor1++];
			 else 
				aux[poz++]=v[contor2++];
			
		 else 
			if (contor1<=mediu) aux[poz++]=v[contor1++];
			else
				aux[poz++]=v[contor2++];
	}
	
	for (contor1=0;contor1<poz;contor1++){
		cout<<aux[contor1]<<' ';
			v[start+contor1]=aux[contor1];}cout<<'\n';

}

void mergesort(int start, int end) { 
	int middle=(start+end)/2;
	if (start==end) return;
	else
	{
		mergesort(start,middle);
		mergesort(middle+1,end);cout<<2;
		merge(start,middle,end);
	}
}

void get_data(){
	in>>n;
	for(int contor=0;contor<n;contor++) in>>v[contor];
}

void print_data(){
	for (int contor=0;contor<n;contor++) out<<v[contor]<<' ';
		
}
int main(){
	get_data();
	mergesort(0,n-1);
	print_data();
return 0;
}