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

const int Nmax = 500005;
const int inf = (1LL << 31) - 1;

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

int n;
int v[Nmax];


/*
	Lomuto.
*/

void QuickSort1(int left, int right) {
	if (right <= left) return;

	int i = left - 1;
	int p = (rand() % (right - left + 1) + left);
	swap(v[p], v[right]);
	p = v[right];

	for (int j = left; j < right; ++j)
		if (v[j] < p) {
			++i;
			swap(v[i], v[j]);
		}
	swap(v[i + 1], v[right]);

	QuickSort1(left, i);
	QuickSort1(i + 2, right);
}


/*
	Lomuto.
	Instead of sending all elements equal to the pivot in one side,
	we divide them equally.
*/

void QuickSort2(int left, int right) {
	if (right <= left) return;

	int i = left - 1;
	int p = (rand() % (right - left + 1) + left);
	swap(v[p], v[right]);
	p = v[right];
	bool on_left = 0;

	for (int j = left; j < right; ++j)
		if (v[j] < p) {
			++i;
			swap(v[i], v[j]);
		}
		else if (v[j] == p) {
			if (on_left) {
				++i;
				swap(v[i], v[j]);
			}
			on_left ^= 1;
		}
	swap(v[i + 1], v[right]);

	QuickSort2(left, i);
	QuickSort2(i + 2, right);
}


/*
	Hoare. Classic. The sentinel is needed so that j doesn't go out of bound.
*/

void QuickSort3(int left, int right) {
	if (right <= left) return;

	int i = left - 1;
	int j = right;
	int p = (rand() % (right - left + 1) + left);
	swap(v[p], v[right]);
	p = v[right];

	while (i < j) {
		do ++i; while (v[i] < p);
		do --j; while (v[j] > p);
		if (i < j) swap(v[i], v[j]);
	}
	swap(v[i], v[right]);

	QuickSort3(left, i - 1);
	QuickSort3(i + 1, right);
}


/*
	Hoare.
	Version without sentinel. Instead of do_while use while_do
	and less than or equal checks (both while check and if check are
	necessary.
*/

void QuickSort4(int left, int right) {
	if (right <= left) return;

	int i = left;
	int j = right;
	int p = v[(rand() % (right - left + 1) + left)];

	while (i <= j) {
		while (v[i] < p) ++i;
		while (v[j] > p) --j;
		if (i <= j) {
			swap(v[i], v[j]);
			++i;
			--j;
		}
	}

	QuickSort4(left, i - 1);
	QuickSort4(i, right);
}

/*
	Partition2 - Ceterchi style.
*/

void QuickSort5(int left, int right) {
	if (right <= left) return;

	int i = left;
	int j = right;
	int p = left;

	while (i < j) {
		while (v[p] <= v[j] && j != p) --j;
		if (v[p] > v[j]) {
			swap(v[p], v[j]);
			p = j;
		}

		while (v[p] >= v[i] && i != p) ++i;
		if (v[p] < v[i]) {
			swap(v[p], v[i]);
			p = i;
		}
	}

	QuickSort5(left, p - 1);
	QuickSort5(p + 1, right);
}


/*
	Insertion sort.
*/

void InsertionSort(int left, int right) {
	for (int i = left + 1; i <= right; ++i) {
		v[0] = v[i];
		int j = i - 1;
		while (v[j] > v[0]) {
			v[j + 1] = v[j];
			--j;
		}
		v[j + 1] = v[0];
	}
}


/*
	Selection sort.
*/

void SelectionSort(int left, int right) {
	for (int i = left; i < right; ++i) {
		int k = i;
		for (int j = i + 1; j <= n; ++j)
			if (v[j] < v[k]) k = j;
		swap(v[k], v[i]);
	}
}


/*
	Bubble sort.
*/

void BubbleSort(int left, int right) {
	for (int j = left + 1; j <= n; ++j)
		for (int i = right; i >= j; --i)
			if (v[i] < v[i - 1])
				swap(v[i], v[i - 1]);
}


/*
	Shell sort.
*/

void ShellSort(int left, int right) {
	int nr_increments = 10;
	int increments[] = { 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524 };

	for (int k = nr_increments - 1; k >= 0; --k) {
		int incr = increments[k];
		for (int i = incr + left; i <= right; ++i) {
			int j = i - incr;
			int x = v[i];
			while (x < v[j] && j >= left) {
				v[j + incr] = v[j];
				j -= incr;
			}
			v[j + incr] = x;
		}
	}
}


int main() {
	in >> n;
	for (int i = 1; i <= n; ++i)
		in >> v[i];

	// Sentinel is needed for QuickSort3
	v[0] = -inf;
	ShellSort(1, n);

	for (int i = 1; i <= n; ++i)
		out << v[i] << ' ';

	return 0;
}