Given a min Heap in the form of an integer array arr of size n. write a program to convert it to max Heap. The expected time complexity is O(n).

Example

Input: arr[] = [1, 2, 4, 3, 6, 5]
Output: arr[] = [6, 3, 5, 1, 2, 4] or any Max Heap formed from input elements
Explanation: The above input min heap can be described in tree form as follows:
         1
      /     \
     2       4
   /   \    /
  3     6  5

The corresponding max heap can be described in tree form as follows:
         6
       /    \
     3        5
   /    \    /  
  1      2  4