#include <iostream>
#include <fstream>
#include <vector>
#define inf (1<<30)
using namespace std;

ifstream f("algsort.in");
ofstream g("algsort.out");

vector<long long> v;
int n;

int i_min(int i, int j)
{   cout << v[i] << "  vs  " << v[j] << " \n";
    if (v[i] < v[j])
        return i;
    else
        return j;
}

void min_heapify(int i)
{
    int l=0, r=0, h;
    if (i*2 <=n) l=i*2;
    if (i*2+1 <=n) r=i*2+1;
    int j = i_min(l, r);
    if (v[j] >= v[i]) return;
                //cout << i << " " << l << " "<<  r << " \n";
                //cin >> h;
    swap(v[i], v[j]);
    min_heapify(j);
    return;
}

long long extract_min()
{
    long long x = v[1];
    swap(v[1], v[n--]);
    min_heapify(1);
    return x;
}
void build_heap()
{
    for(int i=n/2; i>=1; i--)
        min_heapify(i);
    return;
}

void heap_sort()
{
    build_heap();
    int m = n;
    for(int i=1; i<=m; i++)
    {
        g << extract_min() << " ";
    }
    return;
}

int main()
{


    f >> n;
    v.resize(n+1);
    v[0]= inf;
    for(int i=1; i<=n; i++)
    {
        f >> v[i];
    }
    build_heap();
    for(int i=1; i<=n; i++)
        cout << v[i] << " ";
    cout << "\n";

    heap_sort();

    f.close();
    g.close();
    return 0;
}