Den Heap korrigieren

Angenommen, es liegt ein Max-Heap mit n Zahlen vor, bei dem alle Elemente die Max-Heap-Eigenschaft erfüllen – mit Ausnahme der Wurzel. Die Aufgabe besteht darin, diesen Heap so anzupassen, dass schließlich alle Elemente tatsächlich die Max-Heap-Eigenschaft einhalten.

Eingabe

Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl n (1 ≤ n ≤ 100 000).

In der nächsten Zeile stehen n durch Leerzeichen getrennte ganze Zahlen (), die die Werte der Heap-Elemente darstellen.

Ausgabe

Das Programm sollte n durch Leerzeichen getrennte ganze Zahlen ausgeben, die den korrigierten Heap beschreiben.

Beispiele

Erklärung