按频率排序并保持顺序

Swift Hard sorting

任务 «按频率排序并保持顺序»

给定一个整数数组。请按照元素出现频率的降序对其进行排序。如果两个元素具有相同的频率，则它们应按照在原数组中首次出现的顺序排列。请实现一个时间复杂度为 O(n log n) 的算法，并且不要使用带有自定义比较器的内置排序函数。

第一行包含一个整数 n (1 ≤ n ≤ 10^5) — 元素的数量。第二行包含 n 个由空格分隔的整数。

输出n个由空格分隔的整数——排序后的数组。

输入

4
1 2 2 3

输出

2 2 1 3

输入

6
1 2 3 4 5 6

输出

1 2 3 4 5 6

输入

1
7

输出

7

main.swift