Max-heap

Given array of integers. Rearrange its elements so that to get a max-heap.

Input

First line contains number of elements $n(n\le 1000)$. Second line contains $n$ integers, no more than $10^6$ by absolute value.

Output

Print array that corresponds to max-heap.

Examples