#include <fstream>
#include <algorithm>
#include <ctime>
#include <iostream>
#define nmax 500005
using namespace std;
ifstream f("algsort.in");
ofstream g("algsort.out");

void read(int &n, int v[])
{
    f >> n;
    for (int i = 1; i <= n; i++)
        f >> v[i];
}
void write(int &n, int v[])
{
    for (int i = 1; i <= n; i++)
        g << v[i] << ' ';
}
void sort_algorithm(int &n, int v[])
{
    sort(v + 1, v + n + 1);
    write(n, v);
}
void sort_bubble(int &n, int v[])
{
    int ok = 0;
    do{
        ok = 0;
        for (int i = 1; i < n; i++)
            if (v[i] > v[i + 1]) {
                swap(v[i], v[i + 1]);
                ok = 1;
            }
    } while (ok);
    write(n, v);
}
void sort_selection(int &n, int v[])
{
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)
            if (v[i] > v[j])
                swap(v[i], v[j]);
    write(n, v);
}

void sort_quick(int st, int dr, int v[])
{
    int piv = v[dr];
    int i = st;
    for (int j = st; j <= dr; j++) {
        if (v[j] < piv) {
            swap(v[i], v[j]);
            i = i + 1;
        }
    }
    swap(v[i], v[dr]);
}
void sort_heap(int &n, int v[])
{
    for (int i = 2; i <= n; i++) {
        int j = i;
        while (j > 1 && v[j] < v[j / 2]) {
            swap(v[j], v[j / 2]);
            j /= 2;
        }
    }
    for (int i = 1; i <= n; i++) {
        g << v[1] << ' ';
        v[1] = 1<<30;
        int j = 1;
        while (j <= n / 2 && (v[j] > v[j * 2] || v[j] > v[j * 2 + 1])) {
            if (j * 2 + 1 <= n && v[j * 2 + 1] < v[j * 2]) {
                swap(v[j], v[j * 2 + 1]);
                j = j * 2 + 1;
            }
            else {
                swap(v[j], v[j * 2]);
                j = j * 2;
            }
        }
    }
}
int main()
{
    int n, v[nmax] = {0};
    read(n, v);
/**
    srand(time(0));
    for (int i = 1; i <= 10; i++)
        cout << rand() % 10 + 1 << '\n';
    * rand() de la 0 la 32k
     * % n => 0 ... n - 1
     * % n + 1 => 1 ... n
     */
    sort_heap(n, v);

    return 0;
}