题目背景

快速排序用到了分治的思想。

首先在这个序列中随便找一个数作为基准数。为了方便，取中间位置的数为基准数。接下来，需要将这个序列中所有比基准数大的数放在它的右边，比基准数小的数放在它的左边。可以通过“交换”达到这一目的。

继续对左右两个序列做同样操作。

题目描述

输入一个数组的长度n和所有元素，将数组按从小到大的顺序排序。

注：本题为模板题，仅作为教学使用。

输入格式

第一行一个整数n(1≤n≤10^6)；

第二行是n个不大于100000的正整数。

输出格式

n个用空格分隔的整数，为排序后的数组。

输入/输出样例

10
2 7 9 1 6 3 4 1 5 8

1 1 2 3 4 5 6 7 8 9

说明/提示

时间1000ms，内存256MiB