Merge sort for linked lists

Go Hard sorting

Task «Merge sort for linked lists»

Given a singly linked list consisting of integers. It is necessary to implement merge sort for this list. Input data: the number of elements and the elements themselves. Output data: a sorted list printed separated by spaces. Constraints: the number of elements up to 10^5, values in the range from -10^9 to 10^9. It is required to use the merge sort algorithm with O(n log n) complexity and not to use additional arrays for storing values.

Input Format

First line: integer n (1 ≤ n ≤ 10^5) — the number of elements. Second line: n integers separated by spaces.

Output Format

One line: n integers separated by spaces — a sorted list.

Examples

Example 1

INPUT

6
-5 0 10 3 -2 7

OUTPUT

-5 -2 0 3 7 10

main.go