#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
 
bool is_power_of_two(int i)
{
	return (i & (i - 1)) == 0;
}
 
void heap_print(int a[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		if (is_power_of_two(i + 1))
		{
			printf("| ");
		}
		printf("%2d ", a[i]);
	}
	putchar('\n');
}
 
int father_of(int i)
{
	return (i - 1) >> 1;
}
 
bool is_heap(int a[], int n)
{
	for (int i = 1; i < n; ++i)
	{
		if (a[father_of(i)] < a[i]) return false;
	}
	return true;
}
 
void heap_insert(int a[], int i)
{
	int element = a[i];
	int father;
	while ((0 < i) && a[father = father_of(i)] < element)
	{
		a[i] = a[father];
		i = father;
	}
	a[i] = element;
	assert(is_heap(a, i+1));
}
 
int max_child(int a[], int n, int i)
{
	int left_child = (i << 1) + 1;
	if (left_child >= n) return n;
 
	int right_child = left_child + 1;
	/*
	In the rare case where i has only one child, right_child == n.
	Since a[n] == element, the remove loop would terminate correctly,
	so it does not have to be handled explicitly as a special case.
	*/
	return a[left_child] < a[right_child] ? right_child : left_child;
}
 
void heap_remove(int a[], int n)
{
	int maximum = a[0];
	int element = a[n];
	int i = 0;
	int child;
	while (element < a[child = max_child(a, n, i)])
	{
		a[i] = a[child];
		i = child;
	}
	a[i] = element;
	a[n] = maximum;
	assert(is_heap(a, n));
}
 
void heapsort(int a[], int n)
{
	for (int i = 1; i < n; ++i)
	{
		heap_print(a, i);
		heap_insert(a, i);
	}
	heap_print(a, n);
	for (int i = n - 1; i > 0; --i)
	{
		heap_remove(a, i);
		heap_print(a, i);
	}
}
 
void randomize(int a[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		a[i] = 10 + rand() % 90;
	}
}
 
bool is_sorted(int a[], int n)
{
	for (int i = 1; i < n; ++i)
	{
		if (a[i-1] > a[i]) return false;
	}
	return true;
}
 
int sum(int a[], int n)
{
	int s = 0;
	for (int i = 0; i < n; ++i)
	{
		s += a[i];
	}
	return s;
}
 
enum { N = 23 };
 
int main()
{
	int a[N];
	randomize(a, N);
 
	int old_sum = sum(a, N);
	heapsort(a, N);
	int new_sum = sum(a, N);
 
	assert(old_sum == new_sum);
	assert(is_sorted(a, N));
}
 

I2luY2x1ZGUgPGFzc2VydC5oPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPHN0ZGxpYi5oPgoKYm9vbCBpc19wb3dlcl9vZl90d28oaW50IGkpCnsKCXJldHVybiAoaSAmIChpIC0gMSkpID09IDA7Cn0KCnZvaWQgaGVhcF9wcmludChpbnQgYVtdLCBpbnQgbikKewoJZm9yIChpbnQgaSA9IDA7IGkgPCBuOyArK2kpCgl7CgkJaWYgKGlzX3Bvd2VyX29mX3R3byhpICsgMSkpCgkJewoJCQlwcmludGYoInwgIik7CgkJfQoJCXByaW50ZigiJTJkICIsIGFbaV0pOwoJfQoJcHV0Y2hhcignXG4nKTsKfQoKaW50IGZhdGhlcl9vZihpbnQgaSkKewoJcmV0dXJuIChpIC0gMSkgPj4gMTsKfQoKYm9vbCBpc19oZWFwKGludCBhW10sIGludCBuKQp7Cglmb3IgKGludCBpID0gMTsgaSA8IG47ICsraSkKCXsKCQlpZiAoYVtmYXRoZXJfb2YoaSldIDwgYVtpXSkgcmV0dXJuIGZhbHNlOwoJfQoJcmV0dXJuIHRydWU7Cn0KCnZvaWQgaGVhcF9pbnNlcnQoaW50IGFbXSwgaW50IGkpCnsKCWludCBlbGVtZW50ID0gYVtpXTsKCWludCBmYXRoZXI7Cgl3aGlsZSAoKDAgPCBpKSAmJiBhW2ZhdGhlciA9IGZhdGhlcl9vZihpKV0gPCBlbGVtZW50KQoJewoJCWFbaV0gPSBhW2ZhdGhlcl07CgkJaSA9IGZhdGhlcjsKCX0KCWFbaV0gPSBlbGVtZW50OwoJYXNzZXJ0KGlzX2hlYXAoYSwgaSsxKSk7Cn0KCmludCBtYXhfY2hpbGQoaW50IGFbXSwgaW50IG4sIGludCBpKQp7CglpbnQgbGVmdF9jaGlsZCA9IChpIDw8IDEpICsgMTsKCWlmIChsZWZ0X2NoaWxkID49IG4pIHJldHVybiBuOwoKCWludCByaWdodF9jaGlsZCA9IGxlZnRfY2hpbGQgKyAxOwoJLyoKCUluIHRoZSByYXJlIGNhc2Ugd2hlcmUgaSBoYXMgb25seSBvbmUgY2hpbGQsIHJpZ2h0X2NoaWxkID09IG4uCglTaW5jZSBhW25dID09IGVsZW1lbnQsIHRoZSByZW1vdmUgbG9vcCB3b3VsZCB0ZXJtaW5hdGUgY29ycmVjdGx5LAoJc28gaXQgZG9lcyBub3QgaGF2ZSB0byBiZSBoYW5kbGVkIGV4cGxpY2l0bHkgYXMgYSBzcGVjaWFsIGNhc2UuCgkqLwoJcmV0dXJuIGFbbGVmdF9jaGlsZF0gPCBhW3JpZ2h0X2NoaWxkXSA/IHJpZ2h0X2NoaWxkIDogbGVmdF9jaGlsZDsKfQoKdm9pZCBoZWFwX3JlbW92ZShpbnQgYVtdLCBpbnQgbikKewoJaW50IG1heGltdW0gPSBhWzBdOwoJaW50IGVsZW1lbnQgPSBhW25dOwoJaW50IGkgPSAwOwoJaW50IGNoaWxkOwoJd2hpbGUgKGVsZW1lbnQgPCBhW2NoaWxkID0gbWF4X2NoaWxkKGEsIG4sIGkpXSkKCXsKCQlhW2ldID0gYVtjaGlsZF07CgkJaSA9IGNoaWxkOwoJfQoJYVtpXSA9IGVsZW1lbnQ7CglhW25dID0gbWF4aW11bTsKCWFzc2VydChpc19oZWFwKGEsIG4pKTsKfQoKdm9pZCBoZWFwc29ydChpbnQgYVtdLCBpbnQgbikKewoJZm9yIChpbnQgaSA9IDE7IGkgPCBuOyArK2kpCgl7CgkJaGVhcF9wcmludChhLCBpKTsKCQloZWFwX2luc2VydChhLCBpKTsKCX0KCWhlYXBfcHJpbnQoYSwgbik7Cglmb3IgKGludCBpID0gbiAtIDE7IGkgPiAwOyAtLWkpCgl7CgkJaGVhcF9yZW1vdmUoYSwgaSk7CgkJaGVhcF9wcmludChhLCBpKTsKCX0KfQoKdm9pZCByYW5kb21pemUoaW50IGFbXSwgaW50IG4pCnsKCWZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKQoJewoJCWFbaV0gPSAxMCArIHJhbmQoKSAlIDkwOwoJfQp9Cgpib29sIGlzX3NvcnRlZChpbnQgYVtdLCBpbnQgbikKewoJZm9yIChpbnQgaSA9IDE7IGkgPCBuOyArK2kpCgl7CgkJaWYgKGFbaS0xXSA+IGFbaV0pIHJldHVybiBmYWxzZTsKCX0KCXJldHVybiB0cnVlOwp9CgppbnQgc3VtKGludCBhW10sIGludCBuKQp7CglpbnQgcyA9IDA7Cglmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkKCXsKCQlzICs9IGFbaV07Cgl9CglyZXR1cm4gczsKfQoKZW51bSB7IE4gPSAyMyB9OwoKaW50IG1haW4oKQp7CglpbnQgYVtOXTsKCXJhbmRvbWl6ZShhLCBOKTsKCglpbnQgb2xkX3N1bSA9IHN1bShhLCBOKTsKCWhlYXBzb3J0KGEsIE4pOwoJaW50IG5ld19zdW0gPSBzdW0oYSwgTik7CgoJYXNzZXJ0KG9sZF9zdW0gPT0gbmV3X3N1bSk7Cglhc3NlcnQoaXNfc29ydGVkKGEsIE4pKTsKfQo=