#include <stdio.h>
void sift(int *a,int i,int m);
void heapsort(int *t,int n);
main()
{
int a[10000],i,n;
FILE *in,*out;
in=fopen("data.in","r");
out=fopen("heapsort.out","w+");
fscanf(in,"%d\n",&n);
for(i=1;i<=n;i++)
fscanf(in,"%d",&a[i]);
heapsort(a,n);
for(i=1;i<=n;i++)
fprintf(out,"%d",a[i]);
fclose(in);
fclose(out);
}
void sift(int *a,int i,int m)
{int j;
a[0]=a[i];j=2*i;
while(j<=m)
{if(j<m&&(a[j]<a[j+1]))j++;
if(a[0]<a[i])
{a[i]=a[j];i=j;j=2*i;}
else break;
}
a[i]=a[0];
}
void heapsort(int *a,int n)
{int i;
for(i=n/2;i>=1;i--)
sift(a,i,n);
for(i=n;i>=2;i--)
{a[0]=a[1];
a[1]=a[i];
a[i]=a[0];
sift(a,1,i-1);
}
}