#include <fstream.h>
#define MAX 500001

ifstream f("algsort.in");
ofstream g("algsort.out");
int v[MAX],a[MAX];

int main()
{
	int i,j,n,min,aux,p,m=1,pasi,start,stop,dr;
	
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	
	for(i=2;i<=n;i+=2)
		if(v[i]<v[i-1])
			aux=v[i-1], v[i-1]=v[i], v[i]=aux;
		
	pasi=2;
	if(n%2==0)
		p=n/2;
	else
		p=n/2+1;

	while(pasi<=p)
	{
		start=1;
		stop=pasi;
		while(stop<=n)
		{
			i=start;
			j=i+pasi;
			m=1;
			dr=stop+pasi;
			if(dr>n) dr--;
			
			while(i<=stop&&j<=dr)
			{
				if(v[i]<v[j])
					a[m++]=v[i], i++;
				else
					a[m++]=v[j], j++;
			}
			
			while(i<=stop)
				a[m++]=v[i++];
			while(j<=dr)
				a[m++]=v[j++];
			
			m=1;
			for(i=start;i<=dr;i++)
				v[i]=a[m++];
			
			start+=2*pasi;
			stop+=2*pasi;
		}
		pasi=pasi*2;
	}
	
	for(i=1;i<=n;i++)
		g<<v[i]<<" ";
	
	
	f.close();
	g.close();
}