Untitled

#include <iostream>
#include <vector>

using namespace std;

vector <int> heap;
int sz = 0;

int sift_up(int i) {
	while (heap[i] > heap[(i - 1) / 2]) {
		swap(heap[i], heap[(i - 1) / 2]);
		i = (i - 1) / 2;
	}
	return i;
}

int sift_down(int i) {
	while (1) {
		if (2 * i + 1 < sz  && 2 * i + 2 >= sz) {
			if (heap[i] < heap[2 * i + 1]) {
				swap(heap[i], heap[2 * i + 1]);
				i = 2 * i + 1;
			}
			else {
				return i;
			}
		}
		else if (2 * i + 2 < sz) {
			if (heap[2 * i + 2] > heap[2 * i + 1]) {
				if (heap[2 * i + 2] > heap[i]) {
					swap(heap[i], heap[2 * i + 2]);
					i = 2 * i + 2;
				}
				else {
					return i;
				}
			}
			else {
				if (heap[2 * i + 1] > heap[i]) {
					swap(heap[i], heap[2 * i + 1]);
					i = 2 * i + 1;
				}
				else {
					return i;
				}
			}
		}
		else {
			return i;			
		}
	}
}

int add(int x) {
	heap.push_back(x);
	sz++;
	return sift_up(heap.size() - 1);
}

int get_max() {
	return heap[0];
}

pair <int, int> extract_max() {	
	if (sz == 0) {
		return {-1, -1};
	}
	int mx = get_max();
	swap(heap[0], heap[sz - 1]);
	sz--;
	int pos = sift_down(0);
	return {pos, mx};
}

void build_heap(vector <int> &a) {
	for (int i = 0; i < a.size(); i++) {
		heap.push_back(a[i]);
		sz++;
		sift_up(i);
	}
}

void build_heap2(vector <int> &a) {
	for (int i = 0; i < a.size(); i++) {
		heap.push_back(a[i]);
		sz++;
	}
	for (int i = a.size() - 1; i >= 0; i--) {
		sift_down(i);
	}
}

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	build_heap2(a);
	for (int i = 0; i < n - 1; i++) {
		extract_max();
	}
	for (int i = 0; i < n; i++)
		cout << heap[i] << ' ';
}