题目描述

请用快速排序方法对数组进行排序。

输入格式

第一行一个整数 $n$。
第二行 $n$ 个整数 $a_i$。

输出格式

一行 $n$ 个整数，表示排序后的数组，数字之间用空格隔开。

样例

5
4 5 3 1 2

1 2 3 4 5

数据范围

• $1 \le n \le 10^6$
• $1 \le a_i \le 10^6$