#include<bits/stdc++.h>
#define Nmax 500006
#define Dim 20000
using namespace std;
int G[Nmax];
int n,m;

int h[Nmax],tata[Nmax];

void init()
{   int i;
    ifstream fin("algsort.in");
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>G[i];
    fin.close();
}

void CombHeap(int i,int k)     //O(log n)
{
    int tata=i,fiu=i*2;
    int v=G[i];
    while(fiu<=k)
    {
        if(fiu<k)
            if(G[fiu]<G[fiu+1]) fiu++;
        if(v<G[fiu])
        {
            G[tata]=G[fiu];
            tata=fiu;
            fiu=fiu*2;
        }
        else fiu=k+1;
    }
    G[tata]=v;


}

void create_heap()
{
    for(int i=n/2;i;i--)
        CombHeap(i,n);
}


void heapsort()
{
    int aux;
    create_heap();
    for(int i=n;i>1;i--)
    {
        aux=G[1];
        G[1]=G[i];
        G[i]=aux;
        CombHeap(1,i-1);
    }
}

//sortarea are O(M log M)



int main()
{
    long i,j,min_c,max_c,M=0,cost,t;
    i=1;
    init();
    heapsort();
    ofstream fout("algsort.out");
    for(i=1;i<=n;i++)
        fout<<G[i]<<' ';
    fout.close();
    /*while(M<n-1)
    {
        if(Find_compresie(G[i].e1)!=Find_compresie(G[i].e2))
        {
            A[++M]=i;
            Union_ponderare(Find_compresie(G[i].e1),Find_compresie(G[i].e2));
        }
        i++;
    }*/


}