给定你一个长度为 $n$ 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 $n$。

第二行包含 $n$ 个整数（所有整数均在 $1 \sim 10^9$ 范围内），表示整个数列。

输出格式

输出共一行，包含 $n$ 个整数，表示排好序的数列。

数据范围

$1 \le n \le 100000$

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

已按 OJ 可直接使用的 1.in/1.out ... 25.in/25.out 生成 25 组快速排序排序题测试数据（覆盖：有序/逆序导致朴素快排退化、海量重复导致分区死循环、极值、近乎有序、以及多组 n=100000 压力数据）。

下载测试数据（zip）

下面说明每组 k=1..25 分别在卡哪些常见错误：

1. 样例：基础正确性。
2. n=1：边界处理（别越界/别多输出空格）。
3. 已升序小规模：卡“选首/尾为 pivot”的朴素快排退化（递归深度、TLE/栈溢出）。
4. 逆序小规模：同 #3，另一种退化输入。
5. 全相等（50 个）：卡分区实现对重复值处理不当导致死循环/无限递归。
6. 小值域大量重复（1..5）：卡重复值分区、以及错误的三路/二路分区边界。
7. 高低交替（1 与 1e9）：卡比较/交换逻辑错误；也卡某些分区写法在极端两值上出 bug。
8. 包含极值与接近极值：卡 int 溢出式比较器（用减法比较）、以及边界比较错误。
9. 近乎有序 + 少量交换：卡“以为快排对近乎有序一定快”但 pivot 选得差仍退化；也卡实现小 bug。
10. 随机中等规模 n=1000：综合正确性（一般错法在这里就会露馅）。
11. 递增块重复（1 出现 1 次，2 出现 2 次...）：卡重复值、以及分区后递归区间计算错误。
12. 降序块重复（每个值重复 3 次）：卡重复 + 逆序组合；也卡 pivot 固定策略退化。
13. 999 个相同 + 少量不同：强卡重复处理与分区边界（很多错误会把少数不同元素“丢了/错位”）。
14. n=100000 完全升序：终极退化用例，专杀“pivot=首/尾 + 递归快排”（栈溢出/TLE）。
15. n=100000 完全逆序：同 #14。
16. n=100000 全相等：专杀“重复值死循环/无限递归/三路分区写错”。
17. n=100000 值域 1..100 大量重复：卡重复值性能与分区正确性（不三路可能很慢）。
18. n=100000 全范围随机：综合强测（性能 + 正确性）。
19. 锯齿序列（奇偶交错）：卡分区指针推进错误、或递归区间错误。
20. “风琴”形（先升后降）：对某些 pivot 策略也可能退化；卡分区实现 bug。
21. 大量围绕 pivot 的重复（499/500/501 混合）：卡重复值导致分区不平衡、或等于 pivot 的处理错误。
22. 5000 个只从少数几个值中随机选：卡计数/重复处理；也卡输出格式与性能。
23. 2 的幂随机打乱：卡比较/交换正确性（无重复、跨度大）。
24. 素数集合打乱：卡一般排序正确性（无重复，检验纯排序逻辑）。
25. n=100000：极大值与递增小值交错：卡分区极不平衡、递归深度、以及重复与唯一值混合时的边界 bug。

如果你还想我像前面一样把“每组具体用来卡哪种错误代码模板（例如 while 循环条件写错、i/j 指针不动、递归区间少/多 1）”进一步细分，也可以把你常见的错误写法贴一下，我能再针对性补几组更“秒杀”的反例。