#include <iostream>
#include <fstream>
using namespace std;
// max heap pt sortare
void sift(int *heap, int vertex, const int &size) {
int son;
do {
son = 0;
if (2 * vertex <= size) {
son = 2 * vertex;
if (son + 1 <= size && heap[son] < heap[son + 1]) {
++son;
}
if (heap[vertex] >= heap[son]) {
son = 0;
}
}
if (son) {
swap(heap[vertex], heap[son]);
vertex = son;
}
} while (son);
}
void buildHeap(int *heap, const int &size) {
for (int i = size / 2; i > 0; --i) {
sift(heap, i, size);
}
}
void heapSort(int *heap, const int &size) {
buildHeap(heap, size);
for (int i = size; i > 1; --i) {
swap(heap[1], heap[i]);
sift(heap, 1, i - 1);
}
}
int main() {
int N, *v, i;
ifstream in("algsort.in");
in >> N;
v = new int[N + 1];
for (i = 1; i <= N; ++i) {
in >> v[i];
}
in.close();
heapSort(v, N);
ofstream out("algsort.out");
for (i = 1; i <= N; ++i) {
out << v[i] << " ";
}
out.close();
delete[] v;
return 0;
}