Merge Sort

Problem statement

An archive divides a large batch of numbered records into smaller batches. Each batch is sorted before two neighboring batches are merged, allowing the archive to organize the full collection through repeated divide-and-merge steps. Your task Sort the array in nondecreasing order using merge sort. Recursively split the range and merge its sorted halves. Important details Retain all duplicates. During merging, selecting the left entry first on ties preserves stability. Target O(n log n) time and O(n) auxiliary storage. Values can be negative and may already be sorted. The output shows the final order rather than the intermediate passes. Worked example For labels 6, -2, 6, 1, the final order is -2, 1, 6, 6. Both copies of 6 remain because sorting changes positions, not the number of records.

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

1 <= n <= 100000; -1000000000 <= values <= 1000000000.

Sample input

4
6 -2 6 1

Sample output

-2 1 6 6