Given array representation of min Heap, write a program to convert it to max Heap. Expected time complexity is O(n).

Example

Input: A[] = [3 5 9 6 8 20 10 12 18 9]

         3
      /     \
     5       9
   /   \    /  \
  6     8  20   10
 /  \   /
12   18 9 

Output: A[] = [20 18 10 12 9 9 3 5 6 8] or any Max Heap formed from input elements

         20
       /    \
     18      10
   /    \    /  \
  12     9  9    3
 /  \   /
5    6 8