649/Heap-Sort

Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region.

Heap Sort

Author: @037

Compile

sudo g++ -std=c++11 -o HeapSort.exe HeapSort.cpp

Input structure

The input starts with an integer number which indicates the number of elements (integers) to be sorted, n. Then, the elements follow, one per line.

Output structure

Outputs the elements in non-decreasing order. Each element must be followed by ;.

Example

Input

6
5
3
2
1
6
4

Output

1;2;3;4;5;6;