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

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

Массив делится пополам, каждая половина сортируется тем же способом, а две упорядоченные половины сливаются за один проход.

В первой строке $n$ от $1$ до $2 \cdot 10^5$. Во второй — $n$ целых чисел, каждое по модулю не больше $10^9$.

Числа в порядке неубывания.