/**
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];
int n, i;
void insereaza(int i)
{
    while(i/2>=1)
    {
        //i e copilul si i/2  tatal
        if(v[i]>v[i/2])
        {
            swap(v[i],v[i/2]);
        }
        else break;
        i=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;
    while(c<=n)
    {
        if(c+1<=n && v[c+1]>v[c])
        {
            c++;
        }
        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(int i=n;i>=2;i--)
    {
        swap(v[1],v[i]);
         /// corectam heapul cu i-1 elemente "stricat" doar de radacina
        corecteaza(i-1);
    }
    for(int i=1;i<=n;i++)
    {
        fout<<v[i]<<" ";
    }

}