#include <fstream>
using namespace std;
ifstream f("algsort.in");
ofstream g("algsort.out");
void max_heapify(int ,int);
void build_max_heap(int ,int);
void heapsort(int ,int);
int heapsize;
void max_heapify(int h[100],int i)
{
int l=2*i,r=2*i+1,largest;
if(l<=heapsize && h[l]>h[i])
largest = l;
else
largest = i;
if(r<=heapsize && h[r]>h[largest])
largest = r;
if(largest != i)
{
int temp = h[i];
h[i]= h[largest];
h[largest]= temp;
max_heapify(h,largest);
}
}
void build_max_heap(int h[100],int len)
{
heapsize = len;
int i;
for(i =len/2;i>=1;i--)
{
max_heapify(h,i);
}
}
void heapsort(int h[100],int len)
{
int i;
build_max_heap(h,len);
for(i=len;i>=2;i--)
{
int temp1 = h[i];
h[i]= h[1];
h[1]= temp1;
heapsize = heapsize -1;
max_heapify(h,1);
}
}
int main()
{
int h[100],n,i;
f>>n;
for(i=1;i<=n;i++)
{
f>>h[i];
}
heapsize = n;
build_max_heap(h,n);
heapsort(h,n);
for(i=1;i<=n;i++)
{
g<<h[i]<<" ";
}
return 0;
}