Given a max-heap with n numbers, all the elements are guaranteed to satisfy the max-heap property except the root. You are asked to fix the heap and make sure all the numbers in the heap actually satisfy the max-heap property.
Input
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000).
The next line contains n space-separated integers () representing the values of the elements in the heap.
Output
The program should print n space-separated integers representing the fixed heap.
Examples
Input
Output
7
-1 9 7 1 3 6 5
9 5 7 1 -1 6 3
8
-2 7 5 2 1 3 4 1
7 2 5 1 1 3 4 -2
Explanation
Example 1 demonstrated. The left graph represents the starting heap. The right one represents the fixed one.
Example 2 demonstrated. The left graph represents the starting heap. The right one represents the fixed one.