Merge sort

Problem

Sort a list of integers with merge sort that you write yourself (split, sort the halves, merge). Print the sorted numbers on one line.

Example

Input

5
5 2 9 1 7

Output

1 2 5 7 9

Five numbers.

Try the problem first. Open one hint at a time.

Hint 1

Split at the middle and sort each half the same way.

Hint 2

Merge by taking the smaller front item each time, then add what is left.

Write your Python code, run it on the examples and submit it to hidden tests.