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

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

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

输入格式

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

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

输出格式

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

数据范围

$1 \le n \le 100000$

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

行，我按 1..25 给你逐组标注这套“归并排序”数据主要在卡哪些常见错误（后面你再给题，我也都会这样逐组说明）。

（归并排序常见坑：合并时指针/边界写错、剩余元素没拷贝、临时数组覆盖、mid 计算与递归区间 off-by-one、奇数长度处理、重复值处理、输出格式/性能等。）

1. 样例：基础正确性。
2. n=1：递归边界（l==r）处理，别越界/别漏输出。
3. 已升序小规模：卡“合并后写回”逻辑（有些错法会把已排序数据破坏）。
4. 逆序小规模：卡合并逻辑正确性（比较/写回顺序）。
5. 全相等（50 个）：卡合并时 <= / < 条件与指针推进，防止死循环/漏拷贝。
6. 小值域大量重复（1..5）：卡重复值 + 合并剩余段拷贝是否正确（很容易丢元素或重复写）。
7. 高低交替（1 与 1e9）：卡合并时比较与写回是否正确（极端交错最容易暴露错位）。
8. 包含极值与接近极值：卡比较器/类型（避免用减法比较导致溢出），也卡合并边界。
9. 近乎有序 + 少量交换：卡“只在需要时合并”的优化写错（有人做剪枝 a[mid] <= a[mid+1] 但区间边界写错会出错）。
10. 随机 n=1000：综合正确性（一般实现 bug 会在这里暴露）。
11. 递增块重复（i 重复 i 次）：卡大量重复 + 分段大小不均时的合并正确性。
12. 降序块重复：卡重复 + 逆序组合；也卡“临时数组索引”写错（常见）。
13. 999 个相同 + 少量不同：卡极端重复导致“剩余拷贝”错误（比如只拷左半/右半，导致少数元素丢失）。
14. 奇数长度 n=999 随机：专卡 mid/递归区间分割（mid=(l+r)/2 后 [l,mid] [mid+1,r]）以及合并时长度计算，奇数最容易 off-by-one。
15. n=100000 完全升序（压力）：卡性能（O(n log n) 必须过）、也卡某些错误的“每层都重新申请数组”导致超慢/内存炸。
16. n=100000 完全逆序（压力）：卡性能 + 合并正确性（每次合并都走最坏路径）。
17. n=100000 全相等（压力）：强卡重复值处理 + 性能；也卡合并条件写错造成死循环（虽然归并一般不会死循环，但错误推进会）。
18. n=100000 值域 1..100 大量重复（压力）：强卡重复值与“拷贝剩余段”是否完整；也卡输出/IO。
19. n=100000 全范围随机（压力）：综合强测（正确性 + 性能 + 内存）。
20. “风琴形” 1..50000..1（对称）：卡合并过程中的下标/覆盖问题（很容易在中间回写时出错）。
21. 锯齿序列（奇偶交错）：卡合并后写回是否正确、以及临时数组索引是否对（错位特别明显）。
22. 大量 499/500/501 混合并打乱：卡重复值集中在“边界附近”时的合并剩余处理（常见 bug：边界元素重复/丢失）。
23. n=100000：1..50000 与 1e9 交错：卡极端两段分布、以及合并是否会把大值段漏拷贝/写错位置。
24. n=100000：从少数几个值中随机选（含极大值）：强卡大量重复 + 极值；也卡如果有人用减法比较器会溢出风险。
25. n=65536（2 的幂）大量重复的 2^k 并打乱：卡“迭代版归并”层级合并（2 的幂长度最典型），也卡临时数组复用/每层合并段长翻倍的边界写错。

后续你再发题目时，我会同样： 1）给你生成 k.in/k.out 的 zip；2）逐组解释每个数据在卡什么常见错误。