Algoritmo Heap Sort

Heap sort è un algoritmo di ordinamento basato sui confronti che utilizza una struttura dati chiamata heap per ordinare un array. L'idea principale dell'algoritmo consiste nel trasformare gli elementi dell'array in un heap, quindi rimuovere ripetutamente l'elemento più grande o più piccolo dall’heap (a seconda che si tratti di un max-heap o di un min-heap) e spostarlo in fondo all’array, finché l’heap non risulta vuoto.

È richiesto di implementare l'algoritmo di heap sort utilizzando un min-heap.

Input

La prima riga dell'input contiene un singolo intero n (1 ≤ n ≤ 100 000), il numero di elementi.

La riga successiva contiene n interi separati da spazio () che rappresentano i valori da ordinare.

Output

Il programma deve stampare l’array risultante in ordine crescente.

Esempi