Description

Quick Sort is more important one of the eight sorting algorithm, especially in the SDNU ACM-ICPC team, because of ChaoChao’s emphasis. Of course, there are a little students forget it. So we review it together.

Format

Input

The first line is a integer $N$, the next are $N$ numbers.

Output

Ouput your sequence after one trip order.

Samples

8
49
38
65
97
76
13
27
49

27 38 13 49 76 97 65 49