Counting Sort

Problem statement

A stationery store records a small nonnegative category number for every item in a shipment. The stock system can organize the shipment by counting how often each category appears, because the category range is limited even when the shipment is large. Your task Sort the integer array in nondecreasing order using counting sort. Count each value, then use those counts to place every occurrence in the result. Important details Preserve all duplicate values. Zero is a valid category. Target O(n + R) time and O(n + R) space, where R is one more than the maximum value. Use cumulative counts when assigning stable output positions; ordinary comparison sorting is not the requested technique. Worked example For categories [4, 0, 2, 4, 1], the sorted result is [0, 1, 2, 4, 4]. The two items in category 4 remain separate entries.

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; 0 <= values <= 10000.

Sample input

5
4 0 2 4 1

Sample output

0 1 2 4 4