1399 - Is that a Heap?

Time Limit: 1s Memory Limit: 128MB

Submissions: 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次模拟赛