/// se da fun vector, sa se sorteze crescator (heapsort)
#include <fstream>

using namespace std;
/**
1. transformam vecrorul in maxheap
Pentru asta: presupunem ca primul element formeaza un heap cu un singur element
si repetitiv inseram cate un element in heapul format anterior
La general, la pasul i, cu i de la 2, avem deja heap cu primele i-1 elemente si
inseram in acesta si elementul i
**/

int v[500010];
int n, i, c, p, j;
int main () {
    ifstream fin ("algsort.in");
    ofstream fout("algsort.out");

    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i];


    for (i=2;i<=n;i++) {
        j = i;
        while (j>1 && v[j] > v[j/2]) {
            swap(v[j], v[j/2]);
            j /= 2;
        }
    }

    /// acum vectorul dat are structura de heap si costul cu care am facut asta este n log n

    for (i=n;i>=2;i--) {
        swap(v[1], v[i]);
        /// corectez heapul cu i-1 elemente stricat doar de radacina
        p = 1;
        c = 2;
        while (c <= i-1) {
            if (c+1 <= i-1 && v[c+1] > v[c])
                c++;
            if (v[p] < v[c])
                swap(v[p], v[c]);
            else
                break; /// nu e nevoie sa mai cobor

            p = c;
            c = 2*c;
        }
    }
  /**
      10
    /    \
   3      5
 /  \    /
1    2  17

2 3 5 1 10 17
    **/
    for (i=1;i<=n;i++)
        fout<<v[i]<<" ";


    return 0;
}