#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int* a,int* b) {
	int x = *a;
	*a = *b;
	*b = x;
}

void sink(int* v,int n,int i) {
	while (1) {
		if (i*2 <= n && v[i*2] > v[i] && ((i*2+1 <= n && v[i*2] > v[i*2+1]) || i*2+1 > n)) {
			swap(&v[i],&v[i*2]);
			i = i * 2;
			continue;
		}
		if (i*2+1 <= n && v[i*2+1] > v[i] && v[i*2+1] > v[i*2]) {
			swap(&v[i],&v[i*2+1]);
			i = i * 2 + 1;
			continue;
		}
		break;
	}
}

void maxheapify(int* v,int n) {
	int i;
	if (n % 2 == 0) if (v[n] > v[n/2]) swap(&v[n],&v[n/2]);
	for (i=n%2==0?n-1:n;i>1;i-=2) {
		if (v[i] > v[i-1] && v[i] > v[i/2]) { swap(&v[i],&v[i/2]); sink(v,n,i); }
		if (v[i-1] > v[i] && v[i-1] > v[i/2]) { swap(&v[i-1],&v[i/2]); sink(v,n,i-1); }
	}
}

int main() {
	FILE *f = fopen("algsort.in","r");
	int n,*v,i,m;
	fscanf(f,"%d",&n);
	m = n;
	v = (int*)malloc((n+1)*sizeof(int));
	for (i=1;i<=n;i++) fscanf(f,"%d",&v[i]);
	fclose(f);
	maxheapify(v,n);
	for (i=1;i<n;i++) {
		swap(&v[1],&v[m]);
		m--;
		sink(v,m,1);
	}
	f = fopen("algsort.out","w");
	for (i=1;i<=n;i++) fprintf(f,"%d ",v[i]);
	fclose(f);
	free(v);
	//printf("%.3f\n",(float)clock()/CLOCKS_PER_SEC);
	return 0;
}