Сортировка по частоте с сохранением порядка

Rust Сложный sorting

Задача «Сортировка по частоте с сохранением порядка»

Дан массив целых чисел. Необходимо отсортировать его по убыванию частоты вхождения элементов. Если два элемента встречаются одинаковое количество раз, то они должны быть расположены в порядке их первого появления в исходном массиве. Требуется реализовать алгоритм сортировки с временной сложностью O(n log n) и использованием дополнительной памяти O(n).

Формат ввода

Первая строка содержит целое число n (1 ≤ n ≤ 10^5). Вторая строка содержит n целых чисел, разделенных пробелами.

Формат вывода

Выведите n целых чисел, разделенных пробелами — отсортированный массив.

Примеры

Пример 1

ВВОД

3
3 2 1

ВЫВОД

3 2 1

main.rs