Ordenação por frequência mantendo a ordem

Swift Hard sorting

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

Dado um array de números inteiros. Ordene-o em ordem decrescente de frequência de ocorrência dos elementos. Se dois elementos tiverem a mesma frequência, eles devem ser dispostos na ordem de sua primeira aparição no array original. Implemente um algoritmo com complexidade de tempo O(n log n) e não utilize funções de ordenação embutidas com comparadores personalizados.

Formato de Entrada

A primeira linha contém um número inteiro n (1 ≤ n ≤ 10^5) — a quantidade de elementos. 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

4
1 2 2 3

SAÍDA

2 2 1 3

Exemplo 2

ENTRADA

6
1 2 3 4 5 6

SAÍDA

1 2 3 4 5 6

Exemplo 3

ENTRADA

1
7

SAÍDA

7

main.swift