Merge Sort Problem

You are given an integer sequence of length n.

Please sort this sequence in non-decreasing order using merge sort.

Output the sorted sequence in order.

Input Format

The input consists of two lines:

• The first line contains integer n
• The second line contains n integers (all integers range from 1 to 1e9), representing the entire sequence

Output Format

Output one line containing n integers, representing the sorted sequence.

Constraints

1 ≤ n ≤ 100000

Sample Input

5
3 1 2 4 5

Sample Output

1 2 3 4 5