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.