/*
 * =====================================================================================
 *
 *       Filename:  heapsort.cpp
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  07/20/2014 13:49:41
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (), 
 *   Organization:  
 *
 * =====================================================================================
 */

#include <cstdio>
#define nmax 500001

using namespace std;

void swap(int* a, int* b)
{
	int aux = *a;
	*a = *b;
	*b = aux;
}

void maxHeapifyDown(int i, int nr, int* heap)
{
	int l, r, x = i;
	l = i << 1;
	r = l + 1;

	if (l <= nr && heap[l] > heap[i])
		x = l;
	if (r <= nr && heap[r] > heap[x])
		x = r;

	if (x != i)
	{
		swap(&heap[i], &heap[x]);
		maxHeapifyDown(x, nr, heap);
	}
}

void buildMaxHeap(int nr, int* heap)
{
	for (int i = nr / 2; i >= 1; i--)
		maxHeapifyDown(i, nr, heap);
}

void heapsort(int nr, int* heap)
{
	buildMaxHeap(nr, heap);
	for (int i = nr; i >= 2; i--)
	{
		swap(&heap[1], &heap[i]);
		nr--;
		maxHeapifyDown(1, nr, heap);
	}
}

int main(int argc, char* argv[])
{
	int n, a[nmax];
	FILE *in, *out;

	in = fopen("algsort.in", "r");
	out = fopen("algsort.out", "w");

	fscanf(in, "%d", &n);
	for (int i = 1; i <= n; i++)
		fscanf(in, "%d", &a[i]);

	heapsort(n, a);

	for (int i = 1; i <= n; i++)
		fprintf(out, "%d ", a[i]);
	
	fclose(in);
	fclose(out);

	return 0;
}