// ch7344 "鸭子排队" (Duck Queueing) -- lane ch7344_live, SUBMISSION 1.
//
// TASK (from the judge's own page):
// read 4 bytes (LE int n) then 4n bytes (LE ints) from stdin; write 4n bytes to stdout,
// an arrangement of the SAME MULTISET in which a[floor(i/2)] <= a[i] for every i > 1
// (1-indexed). That is exactly the MIN-HEAP property.
// The statement proves ascending sort is always valid, then asks: "有没有更好的方法呢……？"
// => the point of the row is the BETTER method, i.e. O(n) bottom-up heap construction
// instead of an O(n log n) sort.
//
// WHY THIS SHAPE:
// * SPACE: the limit is 800 KB and the statement says an I/O-only program already needs
// 796 KB (400 KB of input array + 400 KB of memory-redirected stdout, both charged to
// us). So there is ONE 400 KB buffer and nothing else: no second array, no recursion,
// no std::vector, no std::sort, and only <stdio.h> ("请尽量避免包含不必要的头文件").
// * TIME: Floyd's bottom-up heapify is O(n) -- <= ~2n comparisons for n = 1e5, i.e. ~8x
// less work than sorting. Both are valid answers; the board ranks by time.
// * The read buffer IS the work buffer IS the write buffer: fread straight into a[],
// heapify a[1..n] in place, fwrite from a+1. a[0] holds n, exactly as the sample does.
//
// CORRECTNESS OF THE SIFT-DOWN (the only place this can go wrong):
// invariant: everything below position i is already a valid min-heap.
// v = a[i]; descend along the SMALLER child while that child is < v; then place v.
// * if we descend, the child (which is < v) moves up into v's old slot => parent < child OK;
// * if we stop, the smaller child is >= v, hence BOTH children are >= v => OK.
// Ties break toward "stop" (a[c] >= v), so equal keys are never reordered further than
// necessary. Any arrangement satisfying the property is a valid answer, so this does not
// have to match a reference output -- see the gate in gate_heapify.py.
#include <stdio.h>
unsigned a[100001];
int main() {
fread(a, 1, sizeof(a), stdin);
unsigned n = a[0];
for (unsigned i = n >> 1; i > 0; --i) {
unsigned v = a[i], j = i, c = j << 1;
while (c <= n) {
if (c < n && a[c + 1] < a[c]) ++c;
if (a[c] >= v) break;
a[j] = a[c];
j = c;
c <<= 1;
}
a[j] = v;
}
fwrite(a + 1, 1, (size_t)n << 2, stdout);
return 0;
}