### 问题描述 ``注意：这道题于宝藏排序Ⅰ的区别仅是数据范围`` 在一个神秘的岛屿上，有一支探险队发现了一批宝藏，这批宝藏是以整数数组的形式存在的。每个宝藏上都标有一个数字，代表了其珍贵程度。然而，由于某种神奇的力量，这批宝藏的顺序被打乱了，探险队需要将宝藏按照珍贵程度进行排序，以便更好地研究和保护它们。作为探险队的一员，肖恩需要设计合适的排序算法来将宝藏按照珍贵程度进行从小到大排序。请你帮帮肖恩。 ### 输入描述 输入第一行包括一个数字 $n$ ，表示宝藏总共有 $n$ 个。 输入的第二行包括 $n$ 个数字，第 $i$ 个数字 $a[i]$ 表示第 $i$ 个宝藏的珍贵程度。 数据保证 $1 \leq n \leq 10^5,1 \leq a[i] \leq 10^9$ 。 ### 输出描述 输出 $n$ 个数字，为对宝藏按照珍贵程度从小到大排序后的数组。 ### 样例输入 ``` 5 1 5 9 3 7 ``` ### 样例输出 ``` 1 3 5 7 9 ```