#include <fstream>
#include <iostream>

using namespace std;

template <class T>
class nod
{
private:
    int pr;
    T key;
public:
    int getpr();
    void setpr(int x);
    T getkey();
    void setkey(T x);
    nod();
    int  operator > (std::string str);
    int  operator < (std::string str);
};

template <class T>
int nod<T>::getpr()
{
    return pr;
}
template <class T>
void nod<T>::setpr(int x)
{
    pr=x;
}
template <class T>
T nod<T>::getkey()
{
    return key;
}
template <class T>
void nod<T>::setkey(T x)
{
    key=x;
}
template<class T>
nod<T>::nod()
{
    pr=0;
}
template<class T>
int  nod<T>::operator > (std::string str)
{
    if(strcmp(this->key,str) > 0)
        return 1;
    return -1;
}
template<class T>
int  nod<T>::operator < (std::string str)
{
    if(strcmp(this->key,str) <= 0 )
        return 1;
        return -1;
}

template<class T>
class heap
{
    int n, m;
    nod<T> q[100];
public:
    void pushdown(nod<T> v[100]);
    void insert(nod<T> x);
    void max_heapify(nod<T> a[100], int i, int n);
    void heapsort(nod<T> a[100], int n);
    void build_maxheap(nod<T> a[100], int n);
    nod<T> extract_max();
    void citire();
    void afisare();
    bool isEmpty () const;
};

template <class T>
bool heap<T>::isEmpty () const
{
    return m == 0;
}

template <class T>
void heap<T>::pushdown(nod<T> v[100])
{
    int k=1,m;
    m=n;
    nod<T> aux;
    while(2*k <m )
    {
        if((2*k+1)<m)
        {
            if(( v[2*k].getpr()<v[k].getpr()) || v[2*k+1].getpr()< v[k].getpr())
            {
                if(v[2*k].getpr()<=v[2*k+1].getpr())
                {
                    aux=v[2*k];
                    v[2*k]=v[k];
                    v[k]=aux;
                    k=2*k;
                }
                else
                {
                    aux=v[2*k+1];
                    v[2*k+1]=v[k];
                    v[k]=aux;
                    k=2*k+1;
                }
            }
            else
                return;
        }
        else if( v[2*k].getpr()<v[k].getpr())
        {
            aux=v[2*k];
            v[2*k]=v[k];
            v[k]=aux;
            k=2*k;
        }
        else
            return;
    }
}
//============================================================
template<class T>
void heap<T>::max_heapify(nod<T> a[100], int i, int n)
{

    int j;
    nod<T> temp;
    temp = a[i];
    j = 2*i;
    while (j <= n)
    {
        if (j < n && a[j+1].getpr() > a[j].getpr())
            j = j+1;
        if (temp.getpr() > a[j].getpr())
            break;
        else if (temp.getpr() <= a[j].getpr())
        {
            a[j/2]=a[j];
            j = 2*j;
        }
    }
    a[j/2]=temp;
    return;
}
template<class T>
void heap<T>::heapsort(nod<T> a[100], int n)
{
    int i;
    nod<T> temp;
    for (i = n; i >= 2; i--)
    {
        temp = a[i];
        a[i] = a[1];
        a[1] = temp;
        max_heapify(a, 1, i - 1);
    }
}

template<class T>
void heap<T>::build_maxheap(nod<T> a[100], int n)
{
    int i;
    for(i = n/2; i >= 1; i--)
    {
        max_heapify(a, i, n);
    }
}

//============================================================
template<class T>
void heap<T>::insert(nod<T> x)
{
    int k;
    nod<T> aux;
    q[m].setkey(x.getkey());
    q[m].setpr(x.getpr());
    k=m;
    while(k>1 && q[k/2].getpr()>q[k].getpr())
    {
        aux=q[k/2];
        q[k/2]=q[k];
        q[k]=aux;
        k=k/2;
    }

    m++;
}
template<class T>
nod<T> heap<T>::extract_max()
{
    nod<T> aux;
    aux.setpr(q[1].getpr());
    aux.setkey(q[1].getkey());
    n--;
    q[1].setkey(q[n].getkey());
    q[1].setpr(q[n].getpr());
    pushdown(q);
    return aux;
}
template<class T>
void heap<T>::citire()
{
    int i,y;
    T x;
    cout<<"\nCate elemente doriti sa inserati: ";
    cin>>n;
    for(i=0; i<n; i++)
    {
        cout<<"a["<<i<<"]=";
        cin>>x;
        q[i].setkey(x);
        cout<<"Prioritate: ";
        cin>>y;
        q[i].setpr(y);
        // insert(q,a);
    }
    cout<<"\nElementele inainte de prelucrare sunt: ";
    for(i=0; i<n; i++)
        cout<<q[i].getkey()<<" ";
    build_maxheap(q,n);
    heapsort(q, n);
    cout<<"\nElementele dupa prelucrare sunt: ";
    for(i=0; i<n; i++)
        cout<<q[i].getkey()<<" ";
}
template<class T>
void heap<T>::afisare()
{
    cout<<"\nMaximul este: "<<q[0].getkey()<<" avand prioriatatea "<<q[0].getpr()<<".";
    extract_max(q);
}

int main ()
{
    ifstream f("algsort.in");
    ofstream g("algsort.out");

    heap<int> priority_queue;

    int N, x;
    
    f >> N;
    for (int i=0;i<N;i++) {
        f >> x;
        
        nod<int> newNode;
        newNode.setpr (x);
        newNode.setkey (x);

        priority_queue.insert (newNode);
    }

    while (!priority_queue.isEmpty ()) {
        nod<int> x = priority_queue.extract_max ();

        g << x.getkey () << " ";
    }

    f.close ();
    g.close ();
}