#include <iostream>
#include <fstream>

using namespace std;

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

//Functie pentru refacerea structurii de heap a subarborelui cu radacina root
//dintr-un heap arr cu n elemente (cei doi fii ai radacinii au deja structura de heap!)
void heapify(int arr[], int n, int root)
{
    //Determinam maximul dintre root si cei 2 fii ai sai
    int largest = root;
    int lc = 2*root + 1;
    int rc = 2*root + 2;

    if (lc < n && arr[lc] > arr[largest])
        largest = lc;

    if (rc < n && arr[rc] > arr[largest])
        largest = rc;

    //Daca unul dintre cei 2 fii contine o valoarea mai mare decat cea din radacina,
    //interschimbam cele doua valori si refacem structura de heap a subarborelui fiului respectiv
    if (largest != root)
    {
        swap(arr[root], arr[largest]);
        heapify(arr, n, largest);
    }
}

//Functie care sorteaza un tablou arr format din n elemente
void heapSort(int arr[], int n)
{
    //Se construieste heap-ul initial
    for (int i = n/2-1; i >= 0; i--)
        heapify(arr, n, i);

    //De n ori efectuam urmatoarele operatii
    for (int i = n-1; i >= 0; i--)
    {
        //Interschimbam valoarea maxima din heap (arr[0])
        //cu ultima valoare din subarborele curemt (arr[i])
        swap(arr[0], arr[i]);

        //Refacem structura de heap a arborelui redus
        heapify(arr, i, 0);
    }
}

//Functie pentru afisarea tabloului
void printArray(int arr[], int n)
{
    for (int i=0; i<n; ++i)
        out << arr[i] << " ";
    out << endl;
}

int main()
{
    int *arr ;
    int n ;

    in >> n;
    arr = new int[n+1];
    for ( int i =0 ; i < n ; i ++)
        in >>arr[i];

    heapSort(arr, n);

    //out << "Tabloul sortat: " << endl;
    printArray(arr, n);

    in.close();
    out.close();
    return 0;
}