#include <iostream>
using namespace std;
void siftDown(int *numbers, int root, int bottom)
{
int maxChild;
int done = 0;
while ((root * 2 <= bottom) && (!done))
{
if (root * 2 == bottom)
maxChild = root * 2;
else if (numbers[root * 2] > numbers[root * 2 + 1])
maxChild = root * 2;
else
maxChild = root * 2 + 1;
if (numbers[root] < numbers[maxChild])
{
int temp = numbers[root];
numbers[root] = numbers[maxChild];
numbers[maxChild] = temp;
root = maxChild;
}
else
done = 1;
}
}
void heapSort(int *numbers, int array_size)
{
for (int i = (array_size / 2) - 1; i >= 0; i--)
siftDown(numbers, i, array_size);
for (int i = array_size - 1; i >= 1; i--)
{
int temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
siftDown(numbers, 0, i - 1);
}
}
int main()
{
int n;
cin >> n;
int* mas = new int[n];
for (int i = 0;i < n;i++)
{
cin >> mas[i];
}
heapSort(mas, n);
for (int i = 0;i < n;i++) {
cout << mas[i] << ' ';
}
delete[] mas;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdm9pZCBzaWZ0RG93bihpbnQgKm51bWJlcnMsIGludCByb290LCBpbnQgYm90dG9tKQp7CiAgICBpbnQgbWF4Q2hpbGQ7IAogICAgaW50IGRvbmUgPSAwOyAKCiAgICB3aGlsZSAoKHJvb3QgKiAyIDw9IGJvdHRvbSkgJiYgKCFkb25lKSkKICAgIHsKICAgICAgICBpZiAocm9vdCAqIDIgPT0gYm90dG9tKSAgCiAgICAgICAgICAgIG1heENoaWxkID0gcm9vdCAqIDI7CiAgICAgICAgZWxzZSBpZiAobnVtYmVyc1tyb290ICogMl0gPiBudW1iZXJzW3Jvb3QgKiAyICsgMV0pCiAgICAgICAgICAgIG1heENoaWxkID0gcm9vdCAqIDI7CiAgICAgICAgZWxzZQogICAgICAgICAgICBtYXhDaGlsZCA9IHJvb3QgKiAyICsgMTsKCiAgICAgICAgaWYgKG51bWJlcnNbcm9vdF0gPCBudW1iZXJzW21heENoaWxkXSkKICAgICAgICB7CiAgICAgICAgICAgIGludCB0ZW1wID0gbnVtYmVyc1tyb290XTsKICAgICAgICAgICAgbnVtYmVyc1tyb290XSA9IG51bWJlcnNbbWF4Q2hpbGRdOwogICAgICAgICAgICBudW1iZXJzW21heENoaWxkXSA9IHRlbXA7CiAgICAgICAgICAgIHJvb3QgPSBtYXhDaGlsZDsKICAgICAgICB9CiAgICAgICAgZWxzZSAKICAgICAgICAgICAgZG9uZSA9IDE7IAogICAgfQp9Cgp2b2lkIGhlYXBTb3J0KGludCAqbnVtYmVycywgaW50IGFycmF5X3NpemUpCnsKCiAgICBmb3IgKGludCBpID0gKGFycmF5X3NpemUgLyAyKSAtIDE7IGkgPj0gMDsgaS0tKQogICAgICAgIHNpZnREb3duKG51bWJlcnMsIGksIGFycmF5X3NpemUpOwoKICAgIGZvciAoaW50IGkgPSBhcnJheV9zaXplIC0gMTsgaSA+PSAxOyBpLS0pCiAgICB7CiAgICAgICAgaW50IHRlbXAgPSBudW1iZXJzWzBdOwogICAgICAgIG51bWJlcnNbMF0gPSBudW1iZXJzW2ldOwogICAgICAgIG51bWJlcnNbaV0gPSB0ZW1wOwogICAgICAgIHNpZnREb3duKG51bWJlcnMsIDAsIGkgLSAxKTsKICAgIH0KfQppbnQgbWFpbigpCnsKICAgIGludCBuOwogICAgY2luID4+IG47CiAgICBpbnQqIG1hcyA9IG5ldyBpbnRbbl07CiAgICBmb3IgKGludCBpID0gMDtpIDwgbjtpKyspCiAgICB7CiAgICAgICAgY2luID4+IG1hc1tpXTsKICAgIH0KCgogICAgaGVhcFNvcnQobWFzLCBuKTsKICAgIGZvciAoaW50IGkgPSAwO2kgPCBuO2krKykgewogICAgICAgIGNvdXQgPDwgbWFzW2ldIDw8ICcgJzsKICAgIH0KCgogICAgZGVsZXRlW10gbWFzOwoKICAgIHJldHVybiAwOwp9