#include <stdio.h>

#define MAX_HEAP_SIZE 524288

int Heap[MAX_HEAP_SIZE];

int father ( int poz ){
      return poz / 2;
}

int left_son ( int poz ){
      return poz * 2;
}

int right_son ( int poz ){
      return poz * 2 + 1;
}

void sift ( int H[], int n, int k ){ /// log n
    int son, aux;

    do {
       son = 0;
       if ( left_son ( k ) <= n ){ /// pozitie valabila
         son = left_son ( k ); /// presupun ca fiul stang este cel care trebuie interschimbat
         if ( right_son ( k ) <= n && H[right_son ( k ) ] > H[son] )
           son = right_son ( k ); /// il punem pe cel mai mare fiu ca fiind noul tata
         if ( H[son] <= H[k] ) /// nu am de ce sa interschimb
           son = 0;
       }

       if ( son ) { /// son > 0 => are sens sa interschimb
         aux = H[son];
         H[son] = H[k];
         H[k] = aux;
         k = son; /// trec la urmatorul in functie de ce am gasit
       }
    }while ( son );
}

void build_heap ( int H[], int n ){

   int i;
   for ( i = n / 2; i > 0; i -- )
      sift ( H, n, i );
}

int main()
{

   FILE *fin, *fout;

   int n;
   int i, aux;

   fin = fopen ( "algsort.in", "r" );
   fscanf ( fin, "%d", &n );

   for ( i = 1; i <= n; i ++ )
      fscanf ( fin, "%d", &Heap[i] );
   fclose ( fin );



   /// heap sort !!!!


   build_heap ( Heap, n ); /// incredibil N * LOG N memorie O ( n ) *ALWAYS*
   for ( i = n; i >= 2; i -- ){
      aux = Heap[i];
      Heap[i] = Heap[1];
      Heap[1] = aux;
      sift ( Heap, i - 1, 1 );
   }

   fout = fopen ( "algsort.out", "w" );
   for ( i = 1; i <= n; i ++ )
      fprintf ( fout, "%d ", Heap[i] );





    return 0;
}