Heap sort algorithm

Heap sort is a comparison-based sorting algorithm that uses a heap data structure to sort an array. The basic idea behind the algorithm is to create a heap out of the array elements, then repeatedly remove the largest/smallest element from the heap (depending on whether the heap is a max-heap or a min-heap) and move it to the end of the array, until the heap is empty.
You are asked to implement the heap sort algorithm using a min-heap.

Input

The first line of the input contains a single integer n (1 ≀ n ≀ 100 000) the number of elements.
The next line contains n space-separated integers () representing the values that need to be sorted.

Output

The program should print the final sorted array in increasing order.

Examples

Input
Output
7 4 3 8 -2 9 0 2
-2 0 2 3 4 8 9
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in