# 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

Β

#### Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 10 MB