//shellsort 5.12.2011
#include<iostream>
#include<fstream>
#include<ctime>
using namespace std;
ifstream fin ("algsort.in");
ofstream fout ("algsort.out");
int n,v[500001];
//long nr1=0,nr2=0; //*nr bucle
void shellsort_clasic()
{
	
	for (int gap=n/2;gap>0;gap/=2)
		for (int i=gap;i<n;i++)
		{
			int j=i;
			while (j-gap>=0 && v[j]<v[j-gap]) //*nr bucle: ++nr1
			{
				int aux=v[j];v[j]=v[j-gap];v[j-gap]=aux;//intersch
				j=j-gap;
			}
		}
}

void shellsort_serie()
{
	int gaps[16] = { 1391376, 463792, 198768, 86961, 33936,
                     13776, 4592, 1968, 861, 336, 
                     112, 48, 21, 7, 3, 1 };	
	//Incerpi & Sedgewick, 1985
	//O(e^sqrt(8*ln(5/2)*ln(N))
	for (int k=2;k<16;k++)
		if (gaps[k]<n/2+1)
		{
			int gap=gaps[k];
			for (int i=gap;i<n;i++)
			{
				int j=i;
				while (j-gap>=0 && v[j]<v[j-gap]) //*nr bucle: ++nr1
				{
					int aux=v[j];v[j]=v[j-gap];v[j-gap]=aux;//intersch
					j-=gap;
				}
			}
		}
}

void shellsort_serie2()
{
	int gaps[14] = { 245917, 106458, 46086, 19951, 8637, 1619, 
					 701, 301, 132, 57, 23, 10, 4, 1 };//<-- Ciura, 2001 
	//O(unknown)
	for (int k=0;k<14;k++)
		if (gaps[k]<n/2+1)
		{
			int gap=gaps[k];
			for (int i=gap;i<n;i++)
			{
				int j=i;
				while (j-gap>=0 && v[j]<v[j-gap]) //*nr bucle: ++nr1
				{
					int aux=v[j];v[j]=v[j-gap];v[j-gap]=aux;//intersch
					j-=gap;
				}
			}
		}
}

void shellsort_serie3()
{
	//termeni: 4^k+3*(2^(k-1))+1 
	//1073790977, 268460033, 67121153, 16783361,
	int gaps[12] = { 4197377, 1050113, 262913, 65921, 16577, 4193, 1073, 281, 
					 77, 23, 8, 1 }; //Sedgewick, 1986
	//O(n^4/3)
	for (int k=0;k<12;k++)
		if (gaps[k]<n/2+1)
		{
			int gap=gaps[k];
			for (int i=gap;i<n;i++)
			{
				int j=i;
				while (j-gap>=0 && v[j]<v[j-gap]) //*nr bucle: ++nr1
				{
					int aux=v[j];v[j]=v[j-gap];v[j-gap]=aux;//intersch
					j-=gap;
				}
			}
		}
}

int main ()
{
	clock_t start=clock();
	fin>>n; for (int i=0;i<n;i++) fin>>v[i]; //citire
	
	//shellsort_clasic(); //worst: O(n^2)
	//shellsort_serie(); //O(e^sqrt(8*ln(5/2)*ln(N))
	//shellsort_serie2(); //O(unknown), best?
	shellsort_serie3(); //O(n^4/3)
	
	for (int i=0;i<n;i++) fout<<v[i]<<' '; //scriere
	//cout<<"\n Nr bucle: "<<nr1<<' '<<nr2; //testing
	cout<<'\n'<<clock()-start;
	fin.close();
	fout.close();
	return 0;
}