Counting sort with order restoration

Java Hard sorting

Task «Counting sort with order restoration»

Given an array of integers. It is necessary to sort it in ascending order using the counting sort algorithm. However, for equal element values, their original relative order must be preserved (stable sort). Output the sorted array. Constraints: array length from 1 to 10^5, element values from -10^4 to 10^4.

Input Format

The first line contains an integer N (1 ≤ N ≤ 100000) — the number of elements. The second line contains N integers separated by spaces — the elements of the array.

Output Format

Output N numbers — a sorted array, separated by spaces.

Examples

Example 1

INPUT

5
3 1 2 1 3

OUTPUT

1 1 2 3 3

Example 2

INPUT

4
-2 0 -2 1

OUTPUT

-2 -2 0 1

Example 3

INPUT

1
42

OUTPUT

42

main.java