Algorithms and Data Structures

Fix the heap

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 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.
Example 2 demonstrated. The left graph represents the starting heap. The right one represents the fixed one.
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue