#include<stdio.h>

int A[500000],H;

void maxheaplify(int *A,int i){
int r,l,lrgst,tmp;
l = 2*i;
r = 2*i+1;

if(l<=H && A[l] > A[i]) lrgst = l;
else lrgst = i;

if(r<=H && A[r] > A[lrgst]) lrgst = r;

if(lrgst != i){
tmp = A[i];
A[i] = A[lrgst];
A[lrgst] = tmp;
maxheaplify(A,lrgst);
}
}

void buildMaxHeap(A){
    int i;
    for(i=H/2;i>=1;i--) maxheaplify(A,i);
}
int main(){

int h,i,j;

scanf("%d",&H);

for(i=1;i<=H;i++){
scanf("%d",&A[i]);

}
buildMaxHeap(A);

for(i=1;i<=H;i++) printf(" %d",A[i]);
printf("\n");
    return 0;
}


/*「節点のキーがその親のキー以下である」という max-ヒープ条件を満たすヒープを、max-ヒープと呼びます。max-ヒープでは、最大の要素が根に格納され、ある節点を根とする部分木の節点のキーは、その部分木の根のキー以下となります。親子間のみに大小関係があり、兄弟間に制約はないことに注意してください。

例えば、下図はmax-ヒープの例です。



与えられた配列から以下の疑似コードに従ってmax-ヒープを構築するプログラムを作成してください。

m
a
x
H
e
a
p
i
f
y
(
A
,
i
)
 は、節点 
i
 を根とする部分木が max-ヒープになるよう 
A
[
i
]
 の値を max-ヒープの葉へ向かって下降させます。ここで 
H
 をヒープサイズとします。

1  maxHeapify(A, i)
2      l = left(i)
3      r = right(i)
4      // 左の子、自分、右の子で値が最大のノードを選ぶ
5      if l ≤ H and A[l] > A[i]
6          largest = l
7      else 
8          largest = i
9      if r ≤ H and A[r] > A[largest]
10         largest = r
11
12     if largest ≠ i　// i の子の方が値が大きい場合
13         A[i] と A[largest] を交換
14         maxHeapify(A, largest) // 再帰的に呼び出し
次の buildMaxHeap(A) はボトムアップに maxHeapify を適用することで配列 
A
 を max-ヒープに変換します。

1 buildMaxHeap(A)
2    for i = H/2 downto 1
3        maxHeapify(A, i)
入力
入力の最初の行に、ヒープのサイズ 
H
 が与えられます。続いて、ヒープの節点の値を表す 
H
 個の整数が節点の番号が 1 から 
H
 に向かって順番に空白区切りで与えられます。

出力
max-ヒープの節点の値を節点の番号が 1 から 
H
 に向かって順番に１行に出力してください。各値の直前に１つの空白文字を出力してください。

制約
1
≤
H
≤
500
,
000
−
2
,
000
,
000
,
000
≤
節
点
の
値
≤
2
,
000
,
000
,
000
入力例 1
10
4 1 3 2 16 9 10 14 8 7
出力例 1
 16 14 10 8 7 9 3 2 4 1 */
