A7960.升序

给定含有 $n$ 个整数的序列，请将这个序列升序排列。

注意：请用归并排序完成

第 $1$ 行输入一个正整数 $n$，第 $2$ 行包含 $n$ 个空格隔开的正整数 $a_i$，为需要进行排序的数，数据保证了 $a_i$ 不超过 $10^9$。

划分时以中间位置左边（包括中间位置）为前半段，中间位置右边为右半段，依次输出每一趟划分后归并的结果。

对于 $100\%$ 的数据，有 $0 < n \leq 10^3$。