Ordenamiento por frecuencia con preservación del orden

Rust Hard sorting

Tarea «Ordenamiento por frecuencia con preservación del orden»

Dado un array de números enteros. Es necesario ordenarlo en orden descendente según la frecuencia de aparición de los elementos. Si dos elementos aparecen la misma cantidad de veces, deben ubicarse en el orden de su primera aparición en el array original. Se requiere implementar un algoritmo de ordenamiento con complejidad temporal O(n log n) y uso de memoria adicional O(n).

Formato de entrada

La primera línea contiene un número entero n (1 ≤ n ≤ 10^5). La segunda línea contiene n números enteros separados por espacios.

Formato de salida

Imprima n números enteros separados por espacios — el array ordenado.

Ejemplos

Ejemplo 1

ENTRADA

3
3 2 1

SALIDA

3 2 1

main.rs