/**
Heap sort

Facem sirul initial maxheap (maximul in varf)
Pentru asta folosim strategia de la sortare prin inserare
bazandu-ne ca avem heap cu i-1 elemente si inseram in ele pe v[i]

Apoi, in mod repetat ducem varful heapului (maximul) la final si apelam o corectare
a heapului ramas cu un element mai putin si stricat doar de radacina (care a fost adusa de la final deci destul de probabil este un element mai mic).

Complexitatea este n log de constanta 2.
**/
#include <fstream>
using namespace std;
int v[500010], w[500010];
int n, i;

void insereaza(int i) {
    while (i/2 >= 1) {
        /// i e copilul si i/2 este tatal
        if (v[i] > v[i/2]) {
            swap(v[i], v[i/2]);
        } else
            break;
        i/=2;
    }
}


/// coboara radacina incat sa se ajunga la un heap corect cu n elemente
/// stricat doar de ea
void corecteaza(int n) {
    int p = 1;
    int c = 2; /// initializam mereu copilul cu fiul stang al parintelui

    while (c <= n) {
        if (c+1 <= n && v[c+1] > v[c])
            c++; /// copilul care se va duce in locul parintelui devine tata pentru fostul frate al sau si ne asiguram ca este mai mare ca el, fiind vorba despre un maxheap
        if (v[p] < v[c]) {
            swap(v[p], v[c]);

        } else
            break;

        p = c;
        c = 2*p;

    }

}

int main () {

    ifstream fin("algsort.in");
    ofstream fout("algsort.out");

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

        /// presupune ca primele i-1 elemente formeaza un maxheap
        /// si il updateaza cu inca un element devenind un maxheap cu i elemente
        insereaza(i);
    }

    /// partea a doua, care pleaca de la un heap cu n elemente
    for (i=n;i>=2;i--) {
        swap(v[1], v[i]);
        /// corectam heapul cu i-1 elemente "stricat" doar de radacina
        corecteaza(i-1);
    }

    for (i=1;i<=n;i++)
        fout<<v[i]<<" ";
}