1399 - Is that a Heap?

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 129

Solved: 38

Description


       Given a sequence S[1..N], you are to rearrange the sequence so that it satisfies the following condition: for each i (1 <= i <= N / 2), S[i] <= S[2*i] and S[i] <= S[2*i+1].


Input


       There are multiple test cases. For each case:



       The first line is a integer N. You are guaranteed that N = 2m - 1 for some non-negative number m.



       The next line contains N numbers representing S[i]



       1 <= N <= 65535, S[i] <= 1,000,000,000


Output


       For each case, output the result sequence, if there are multiple solutions output the lexicographically largest one.


sample input
3
1 2 10
sample output
1 10 2
hint
source
Orz教主第2次模拟赛
© 2015 HUST ACMICPC TEAM. All Right Reserved.