/*  Heapsort cu Max-Heap mai ineficient folosind "urcarea" in sus a nodurilor
    Daca urcam in sus trebuie sa luam fiecare nod la rand, inclusiv frunzele, astfel incat complexitatea heapify-ului devine O(log n)
*/
#include <stdio.h>

using namespace std;

void interschimba(int &a, int &b) {
    int aux = a;
    a = b;
    b = aux;
}

void sus(int pos, int *heap) {
    while (pos > 1 && heap[pos] > heap[pos / 2]) {
        interschimba(heap[pos], heap[pos / 2]);
        pos = pos / 2;
    }
}

void jos(int pos, int *heap, int dim_heap) {
    while (true) {
        // daca nu are fii inseamna ca e pe pozitia corecta (avand in vedere ca valoarea de unde a venit era mai mica)
        if (pos * 2 > dim_heap)
            return;
        if (pos * 2 == dim_heap) { // are doar un fiu
            if (heap[pos] < heap[pos * 2]) {
                interschimba(heap[pos], heap[pos * 2]);
                pos *= 2;
            }
            else
                return;
        }
        else { // daca a ajuns pana aici inseamna ca are 2 fii
            int max_fiu_pos = pos * 2; // presupunem ca fiul stang e mai mare
            if (heap[pos * 2] < heap[pos * 2 + 1])
                max_fiu_pos++;  // al doilea fiu este cel cu care trebuie sa schimbam (max_fiu_pos++ echivalent cu max_fiu_pos = pos * 2 + 1)
            if (heap[pos] < heap[max_fiu_pos]) {
                interschimba(heap[pos], heap[max_fiu_pos]);
                pos = max_fiu_pos;
            }
            else
                return;
        }
    }
}

// transforma vectorul intr-un vector "heap" tragand celelalte elemente in jos pentru ca elementul curent sa fie in pozitie buna
void heapify(int *heap, int dim_heap) {
    int start = 1;
    while (start <= dim_heap) {
        sus(start, heap);
        start++;
    }
}

int main() {
	freopen("algsort.in", "r", stdin);
	freopen("algsort.out", "w", stdout);
	int n;
	scanf("%d", &n);
	int v[500001];
	for (int i = 1; i <= n; i++)
        scanf("%d", &v[i]);
    heapify(v, n);
    for (int i = 2; i <= n; i++) {
        interschimba(v[1], v[n - i + 2]); // punem cel mai mare element in capatul vectorului, dupa n - 1 pasi obtinem vectorul sortat complet
        jos(1, v, n - i + 1);             // interschimbarea a stricat o parte din heap, trebuie sa punem elementul interschimbat acolo unde ii e locul
    }
    // vectorul obtinut e sortat crescator, deci mai ramane doar sa il scriem
    for (int i = 1; i <= n; i++)
        printf("%i ", v[i]);
	return 0;
}