#include<stdio.h>
#define nr_elem 500001

using namespace std;

FILE *c,*d;
int heap[nr_elem];


void swap(int &a,int &b)
{
	int aux;
	aux=a;
	a=b;
	b=aux;
}

void min_heapify_down(int n,int i)                       //n reprezinta numarul de elemente din heap
{
	int l,r,poz;
	poz=i;
	l=i<<1;
	r=l+1;
	if(l<=n&&heap[l]<heap[poz])
		poz=l;
	if(r<=n&&heap[r]<heap[poz])
		poz=r;
	if(poz!=i)
	{
		swap(heap[i],heap[poz]);
		min_heapify_down(n,poz);
	}
}

void build_min_heap(int n)
{
	int i;
	for(i=n>>1;i>=1;i--)
		min_heapify_down(n,i);
}

void heapsort(int n)
{
	int i,nr;
	nr=n;
	build_min_heap(n);
	for(i=n;i>=1;i--)
	{
		fprintf(d,"%d ",heap[1]);
		heap[1]=heap[nr];
		nr--;
		min_heapify_down(nr,1);
	}
}

int main()
{
	int i,nr_elemente;
	c=fopen("algsort.in","r");
	d=fopen("algsort.out","w");
	fscanf(c,"%d",&nr_elemente);
	for(i=1;i<=nr_elemente;i++)
		fscanf(c,"%d",&heap[i]);
	heapsort(nr_elemente);
	fclose(c);
	fclose(d);
}