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

Swift Сложный sorting

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

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

Формат ввода

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

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

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

Примеры

Пример 1

ВВОД

4
1 2 2 3

ВЫВОД

2 2 1 3

Пример 2

ВВОД

6
1 2 3 4 5 6

ВЫВОД

1 2 3 4 5 6

Пример 3

ВВОД

1
7

ВЫВОД

7

main.swift