#include <algorithm>
#include <math.h>
using namespace std;

const int Nmax = 500005;
const int Lmax = 50000;

int n, m;
int v[Nmax];
int batog[Lmax];
int interval_len;
int nr_interval;

void update_interval(int k) {
	// Get maximum element from an interval
	int t = (k - 1) * interval_len;
	int x = t + 1;
	for (int j = 2; j <= interval_len && j + t <= n; ++j)
		if (v[x] < v[t + j])
			x = t + j;
	batog[k] = x;
}

int main() {
	freopen("algsort.in", "r", stdin);
	freopen("algsort.out", "w", stdout);


	scanf("%d", &n);
	m = n;
	for (int i = 1; i <= n; ++i)
		scanf("%d", &v[i]);

	// Set interval length and number of intervals
	interval_len = sqrt(n) * 2;
	if (!interval_len)
		interval_len = 1;
	nr_interval = n / interval_len;
	if (nr_interval * interval_len < n) ++nr_interval;

	// Build initial Smen of Batog array
	for (int i = 1; i <= nr_interval; ++i)
		update_interval(i);

	while (n) {
		// Get maximum element from remaining vector
		int x = 1;
		for (int i = 2; i <= nr_interval; ++i)
			if (v[ batog[x] ] < v[ batog[i] ])
				x = i;
		// Swap it with the last element and update its interval
		swap(v[ batog[x] ], v[n]); update_interval(x);

		// Decrease vector size by one, check if the last interval still exists
		// and if so update it
		--n;
		if (n == interval_len * (nr_interval - 1))
			--nr_interval;
		else
			update_interval(nr_interval);
	}

	// Print sorted vector
	for (int i = 1; i <= m; ++i)
		printf("%d ", v[i]);
	printf("\n");

	return 0;
}