#define _CRT_SECURE_NO_DEPRECATE

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define MAX_HEAP_SIZE 12000

typedef int Heap[MAX_HEAP_SIZE];

int left_child(int node) {
	return 2 * node + 1;
}

int right_child(int node) {
	return 2 * node + 2;
}

int parent(int node) {
	return (node - 1) / 2;
}

int max(Heap H) {
	return H[0];
}

void swap(int *first, int *second) {
	int temp = *first;
	*first = *second;
	*second = temp;
}


void sift(Heap H, int N, int K) {
	int child;
	do {
		child = 0;
		if (left_child(K) < N) {
			child = left_child(K);

			if (right_child(K) < N && H[right_child(K)] > H[left_child(K)]) {
				child = right_child(K);
			}

			if (H[child] <= H[K]) {
				child = 0;
			}
		}

		if (child) {
			swap(&H[K], &H[child]);
			K = child;
		}

	} while(child);

}

void build_max_heap(Heap H, int N) {
	for (int i = parent(N); i >= 0; --i) {
		sift(H, N, i);
	}
}

void heapsort(Heap H, int N) {

	for (int i = N-1; i >= 1; --i) {
		swap(&H[0], &H[i]);
		sift(H, i, 0);
	}

}



int main() {
	FILE *raw_data = fopen("algsort.in", "r");
	FILE *sorted_data = fopen("algsort.out", "w");

	int size;
	fscanf(raw_data, "%d", &size);

	Heap heap;
	for (int counter = 0; counter < size; counter++) {
		fscanf(raw_data, "%d", &heap[counter]);
	}

	build_max_heap(heap, size);
	heapsort(heap, size);
	
	for (int counter = 0; counter < size; counter++) {
		fprintf(sorted_data, "%d ", heap[counter]);
	}


//	getchar();
	return 0;
}