题目描述

请用归并排序的方法对数组进行排序。

输入格式

第一行一个整数 $n$。
第二行 $n$ 个非负整数 $a_i$。

输出格式

一行 $n$ 个整数，表示排序后的数组，数字之间用空格隔开。

样例

6
1 3 2 5 4 6

1 2 3 4 5 6

数据范围

• $n \le 10^6$
• $0 \le a_i \le 10^6$