Heapify the Heap

There 2 main operations that can be performed on a Heap: we can add an element, and we can remove the root node from the heap.

After performing each of the operations, we need to make sure that the heap properties are not violated.

When removing the root, we should go from the top to the very bottom of the heap modifying it and fixing up the structure to make sure all the parent nodes have a larger value than their child nodes (for max heap).

When Adding an element, we need to go from the bottom to the very top and modify the structure making sure that all the parent nodes have a larger value than the child nodes.

Insert a New Element Into a Heap

To insert a new value, we first add the value at the end of the array, and then the heap property is restored by repeatedly swapping the newly inserted item with its parent if the heap property is not satisfied for the child and the parent:

heap = [None, 8, 5, 7, 1, 1, 6, 3, 1] # Initial heap
heap.append(6)                        # Add a new element with a value of 6

# Float up and fix the heap property
node = len(heap) - 1                  # The index of the current node
while node > 1:                       # While we haven't reached the root
    parent = node // 2                # Get the index of the parent node
    if heap[node] > heap[parent]:     # If the heap structure is not correct
        heap[node], heap[parent] = heap[parent], heap[node]
    else:                             # If the structure is correct
        break                         # Then the above ones are also in place => stop
    node //= 2                        # Move to the parent node

Delete the Root Element of a Heap

To delete the root element, it is first replaced with the last item in the array, and then the heap property is restored by repeatedly swapping the node with its largest child (in case of a max-heap) until the node is in its correct position:

heap = [None, 8, 5, 7, 1, 1, 6, 3, 1] # Initial heap
heap[1], heap[-1] = heap[-1], heap[1] # Swap the root with the last element
heap.pop()                            # Remove the last element (previously root)

# Descend and fix the heap property
node = 1                              # The index of the current node
while node < len(heap):               # While we haven't reached the end
    left = heap[2 * node] if 2 * node < len(heap) else float('-inf')
    right = heap[2 * node + 1] if 2 * node + 1 < len(heap) else float('-inf')
    
    # If the heap property is not violated => stop here
    if heap[node] >= left and heap[node] >= right:
        break
    
    # If left > right => We should move in the left direction
    if left > right:
        heap[2 * node], heap[node] = heap[node], heap[2 * node]
        node = 2 * node
    else:
        heap[2 * node + 1], heap[node] = heap[node], heap[2 * node + 1]
        node = 2 * node + 1

Challenge: Fix the Heap

Given a min-heap with n numbers, all the n-1 numbers are guaranteed to satisfy the min-heap property. The n-th number might violate the property. You are asked to fix the heap to make sure all the numbers in the heap actually satisfy the min-heap property.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ ).

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 2 5 4 3 6 -3	-3 2 1 4 3 6 5
6 5 6 9 20 10 8	5 6 8 20 10 9

Explanation

Example 1

Example 2