/// HeapSort (R)
/// IA CERTIFIED: PROBLEMA DE 100 DE PUNCTE !! (Conform ALGSORT)

#include <fstream>
#define NIL 500001 /// replace NIL with whatever the hell you want
/// as the maximum size of the list to be sorted

using namespace std;

int a[NIL];
int heap_size;
int length;

bool compare (int a, int b)
{
    return a > b;
}

bool compare_inverse (int a, int b)
{
    return a < b;
}

int parent (int i)
{
    return i/2;
}

int left (int i)
{
    return 2*i;
}

int right (int i)
{
    return 2*i+1;
}

void max_heapify (int a[NIL], int i)
{
    int l=left(i);
    int r=right(i);
    int largest;
    if(l<=heap_size && compare(a[l],a[i])) /// COMPARISON !!
        largest=l;
    else
        largest=i;
    if(r<=heap_size && compare(a[r],a[largest])) /// COMPARISON !!
        largest=r;
    if(largest!=i)
    {
        int aux=a[i];
        a[i]=a[largest];
        a[largest]=aux;
        max_heapify(a,largest);
    }
}

void build_max_heap (int a[NIL])
{
    heap_size=length;
    int i;
    for(i=length/2; i>=1; i--)
        max_heapify(a,i);
}

void heap_sort(int a[NIL])
{
    build_max_heap(a);
    int i, aux;
    for(i=length;i>=2;i--)
    {
        aux=a[1];
        a[1]=a[i];
        a[i]=aux;
        heap_size--;
        max_heapify(a,1);
    }
}

int main()
{
    ifstream fin ("algsort.in");
    fin>>length;
    int i;
    for(i=1; i<=length; i++)
        fin>>a[i];
    fin.close();
    heap_sort(a);
    ofstream fout ("algsort.out");
    for(i=1; i<=length; i++)
        fout<<a[i]<<' ';
    fout.close();
    return 0;
}