题目背景

Special for beginners, ^_^

题目描述

在古老的图书馆里，书籍的编号乱成一团。

图书管理员决定使用一种神秘的“分而治之”魔法：

把序列分成左右两半

分别对左右两边排序

再把两个有序序列合并

这就是传说中的“归并魔法”。

现在给你一个整数序列，请你用递归方式实现归并排序，并输出排序后的结果。

输入格式

第一行一个整数 n (1≤n≤10^5) 第二行 n 个整数ai（0≤a_i≤10^9）

输出格式

输出排序后的序列

样例

5
5 3 1 4 2

1 2 3 4 5

样例解释

在该样例中，序列为 5 3 1 4 2。归并排序首先将序列不断二分，直到每个子区间只剩一个元素。随后从底向上进行合并：先将 [5] 和 [3] 合并为 [3 5]，再与 [1] 合并为 [1 3 5]；右侧 [4] 和 [2] 合并为 [2 4]。最后将两个有序序列 [1 3 5] 和 [2 4] 合并，得到最终有序结果 [1 2 3 4 5]。因此输出为 1 2 3 4 5。