Max Heapify Transformation

You are given an array of integers. Your task is to rearrange the array into a max-heap. In a max-heap, every node (indexed from 0) satisfies the heap property:

\( arr[i] \ge arr[2i+1] \) and \( arr[i] \ge arr[2i+2] \) (if these children exist).

Output the transformed array as a space‐separated list on a single line.

inputFormat

The first line contains an integer \( n \), the number of elements in the array. The second line contains \( n \) space-separated integers representing the elements of the array.

outputFormat

Output the array transformed into a max-heap. The output should be a single line containing \( n \) space-separated integers, where the maximum element is at the root (the first element).

6
1 3 6 5 9 8

9 5 8 1 3 6