Ordenação por contagem com restauração da ordem

Java Hard sorting

Tarefa «Ordenação por contagem com restauração da ordem»

Dado um array de números inteiros. É necessário ordená-lo em ordem crescente usando o algoritmo de ordenação por contagem (counting sort). Porém, para valores iguais de elementos, deve-se manter sua ordem relativa original (ordenação estável). Imprima o array ordenado. Restrições: comprimento do array de 1 a 10^5, valores dos elementos de -10^4 a 10^4.

Formato de Entrada

A primeira linha contém um número inteiro N (1 ≤ N ≤ 100000) — a quantidade de elementos. A segunda linha contém N números inteiros, separados por espaços — os elementos do array.

Formato de Saída

Imprima N números — o array ordenado, separados por espaços.

Exemplos

Exemplo 1

ENTRADA

5
3 1 2 1 3

SAÍDA

1 1 2 3 3

Exemplo 2

ENTRADA

4
-2 0 -2 1

SAÍDA

-2 -2 0 1

Exemplo 3

ENTRADA

1
42

SAÍDA

42

main.java