Cho dãy số nguyên dương \(a_1, a_2, \ldots, a_n\), hãy sắp xếp dãy đã cho bằng thuật toán sắp xếp trộn.

Input

• Dòng đầu chứa số nguyên dương \(n\) \((n \le 2\cdot 10^5)\).

• Dòng thứ hai chứa \(n\) số \(a_1, a_2, \ldots, a_n\) \((1\le a_i\le 10^9)\)

Output

• Ghi ra dãy đã được sắp xếp tăng dần.

Example

5
3 4 2 1 3

1 2 3 3 4