#include<stdio.h>
#include<stdlib.h>
typedef struct heap_vector {
	int *v;
	int dim;
	int cap;
} Heap;
Heap* create(int *values, int dim, int cap) {
	Heap *h = malloc(sizeof(Heap));
	h->v = malloc(cap * sizeof(int));
	h->dim = dim;
	int i;
	for(i = 0 ; i < dim ; i++ )
		h->v[i] = values[i];
	return h;

}
void freemem(Heap *h) {
	free(h->v);
	free(h);
}
int Parinte(Heap *h,int poz) {
	if (poz)
		return (poz-1)/2;
	return -1;
}
int DescS(Heap *h,int poz) {
	if ( h->dim > 2*poz + 1 )
		return 2*poz + 1;
	return -1;
}
int DescD(Heap *h,int poz) {
	if ( h->dim > 2*poz + 2 ) 
		return 2*poz + 2;
	return -1;
}
int min3(int a,int b,int c) {
	if(a <= b && a <= c)
		return a;
	if(b <= c && b <= a)
		return b;
	return c;
}
void Coboara(Heap *h,int poz) {
	int min,newpoz,aux;
	for(;;) {
		if(DescD(h,poz)<0 && DescS(h,poz)<0)
			return;
		if(DescD(h,poz)<0)
			if(h->v[poz] < h->v[DescS(h,poz)])
				return;
			else
				newpoz = DescS(h,poz);
		else		
			if(DescS(h,poz)<0)
				if(h->v[poz] < h->v[DescD(h,poz)])
					return;
				else
					newpoz = DescD(h,poz);
			else {
				min = min3(h->v[poz],h->v[DescS(h,poz)],h->v[DescD(h,poz)]);
				if(min == h->v[poz])	
					return;
				if(min == h->v[DescD(h,poz)])
					newpoz = DescD(h,poz);
				else
					newpoz = DescS(h,poz);
			}
	aux = h->v[poz];
	h->v[poz] = h->v[newpoz];
	h->v[newpoz] = aux;
	poz = newpoz;
	}
}
void Urca(Heap *h,int poz) {
	int aux,newpoz;
	for(;;) {
		if(Parinte(h,poz) == -1)
			return;
		if(h->v[poz] < h->v[Parinte(h,poz)]) {
			newpoz = Parinte(h,poz);
			aux = h->v[poz];
			h->v[poz] = h->v[newpoz];
			h->v[newpoz] = aux;
			poz = newpoz;
		}
		else
			return;
	}
}
int Minim(Heap *h) {
	return h->v[0];
}
int ExtrageMinim(Heap *h) {
	int aux,min;
	min = h->v[0];
	aux = h->v[0];
	h->v[0] = h->v[h->dim - 1];
	h->v[h->dim-1] = aux;
	h->dim --;
	Coboara(h,0);
	return min;
}
void AdaugaValoare(Heap *h,int val) {
	h->dim ++;
	h->v[h->dim-1] = val;
	Urca(h,h->dim-1);
}
void afisare(Heap *h) {
	int i;
	for(i = 0 ; i < h->dim ; i++ ) 
		printf("%d ",h->v[i]);
	printf("\n");
}
Heap* ConstruiesteHeap(int *values,int dim,int cap) {
	Heap *h = create(values,dim,cap);
        int i;
	for(i = h->dim / 2 -1; i >=0 ; i--) {
		Coboara(h,i);
	}
	return h;
}
int* HeapSort(Heap *h) {
	int *a=malloc(h->dim*sizeof(int));
	int i,n;
	n = h->dim;
	for(i = 0 ; i < n ; i++)
		a[i] = ExtrageMinim(h);
	return a;
}
int main() {
	int *a;
	int *b,i,n;
	FILE *s = fopen("algsort.in","r");
	FILE *d = fopen("algsort.out","w");
	fscanf(s,"%d",&n);
	a = malloc(n * sizeof(int));
	for(i = 0 ; i < n ; i++)
		fscanf(s,"%d",&a[i]);
	Heap *h = ConstruiesteHeap(a,n,n);
	b = HeapSort(h);
	for(i = 0 ; i < n ; i++)
		fprintf(d,"%d ",b[i]);
//	Urca(h,5);
//	printf("%d\n",ExtrageMinim(h));
//	afisare(h);
	freemem(h);
	free(a);
}