問題文

長さ N の配列 [A_1, A_2, \cdots, A_N] が与えられます。

書籍に記されている「マージソートを行う未完成のプログラム」を元に、配列を昇順に並び替えるプログラムを作成してください。

制約

smallと名前がついているテストケースを正答することで、満点の 50 \% を得ることができます。 smallのテストケースは以下の制約を満たします。

• 2 \leq N \leq 2000
• 1 \leq A_i \leq 10^9
• 入力はすべて整数

さらに以下の制約を満たすテストケースを正答することで、満点を得ることができます。

• 2 \leq N \leq 200000
• 1 \leq A_i \leq 10^9
• 入力はすべて整数

入力例 1

3
3 1 2

出力例 1

1 2 3

入力例 2

10
658 299 47 507 122 969 449 68 513 800

出力例 2

47 68 122 299 449 507 513 658 800 969