Ordenação por frequência mantendo a ordem

Rust Hard sorting

Tarefa «Ordenação por frequência mantendo a ordem»

Dado um array de números inteiros. É necessário ordená-lo em ordem decrescente de frequência de ocorrência dos elementos. Se dois elementos ocorrem o mesmo número de vezes, eles devem ser dispostos na ordem de sua primeira aparição no array original. É necessário implementar um algoritmo de ordenação com complexidade de tempo O(n log n) e uso de memória adicional O(n).

Formato de Entrada

A primeira linha contém um número inteiro n (1 ≤ n ≤ 10^5). A segunda linha contém n números inteiros separados por espaços.

Formato de Saída

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

Exemplos

Exemplo 1

ENTRADA

3
3 2 1

SAÍDA

3 2 1

main.rs