Sort List (Linked List)

Problem statement

A courier stores delivery priorities in a singly linked chain. The dispatch system needs the chain ordered from lowest to highest priority without converting it into an array for sorting. Your task Sort the linked list in nondecreasing order in O(n log n) time. Build a singly linked list from the input values and perform the operation on its nodes. Important details Retain every node, including duplicate priorities. Reconnect next pointers instead of sorting a copied array. An iterative bottom-up merge sort can use O(1) auxiliary space; recursive merging may use call-stack space. An empty chain is valid. Worked example The chain 4 -> -1 -> 2 -> 4 becomes -1 -> 2 -> 4 -> 4. Duplicate priorities represent separate deliveries and both remain.

Input format

The first line contains n. The next line contains n space-separated integers; for n = 0 this line may be empty.

Output format

Print the resulting values in order, separated by spaces. Print EMPTY if there are no values.

Constraints

0 <= n <= 50000; -100000 <= values <= 100000.

Sample input

4
4 -1 2 4

Sample output

-1 2 4 4