Heap Sort Algorithm

This problem requires you to implement the heap sort algorithm to sort an array of integers in non-decreasing order. The heap sort algorithm is based on the binary heap data structure. In a binary heap, if an element is at index i, its left child is at index \(2i+1\) and its right child at index \(2i+2\). You need to read the input from stdin and output the sorted array to stdout.

Your task is to construct a max-heap from the unsorted array, and then repeatedly extract the maximum element and rebuild the heap until the array is completely sorted in ascending order.

inputFormat

The input consists of two lines. The first line contains a single integer (N) representing the number of elements in the array. The second line contains (N) space-separated integers.

outputFormat

Output a single line containing the (N) sorted integers in non-decreasing order, separated by a single space.## sample

5
4 1 3 9 7

1 3 4 7 9