ヒープの修正

与えられた n 個の要素からなる max-heap は、根以外のすべての要素が max-heap の性質を満たしていることが保証されています。あなたの役割は、根を含むすべての要素が正しく max-heap の条件を満たすようにヒープ全体を修正することです。

入力

最初の行には、整数 n (1 ≤ n ≤ 100 000) が与えられます。

次の行には、ヒープの要素の値を表す n 個の整数 () が空白区切りで与えられます。

出力

修正後のヒープを表す n 個の整数を空白区切りで出力してください。

例

解説