Сортировка слиянием

Отсортируйте данный массив, используя сортировку слиянием.

Входные данные

Первая строка входных данных содержит количество элементов в массиве N, N ≤ 10⁵. Далее идет N целых чисел, не превосходящих по абсолютной величине 10⁹.

Выходные данные

Выведите эти числа в порядке неубывания.

Примеры

Входные данные

2
3 1

Выходные данные

1 3

Задача на informatics