Quick Sort

Problem statement

A dispatch center organizes numbered parcels by choosing a pivot parcel and separating smaller and larger labels around it. The center repeats this partitioning process within the remaining sections until the loading order is sorted. Your task Sort the array in nondecreasing order using quick sort. Partition around a pivot, then sort the resulting subranges. Important details Duplicate labels must remain. Use a pivot strategy that avoids systematically poor partitions on sorted input; expected time should be O(n log n). An empty partition requires no recursive work. 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