Background

You must solve this problem by hand-writing heap sort.

Description

Suppose $n$ numbers are stored in A[1..n]. We can use a heap to sort them from smallest to largest; this sorting method is called "heap sort".

Format

Input

The input has two lines. The first line is $n$, and the second line holds $n$ integers (positive integers smaller than 1000), separated by single spaces. $1\le n\le 100$.

Output

One line: the $n$ numbers sorted from smallest to largest, also separated by single spaces.

Samples

5
2 3 5 1 4

1 2 3 4 5

Limitation

1s, 1024KiB for each test case.