EN
RU
ES
ZH
FR
DE
PT
AR
HI
Sorting by frequency while preserving order
Swift
Hard
sorting
Task «Sorting by frequency while preserving order»
Given an array of integers. Sort it in descending order of the frequency of occurrence of elements. If two elements have the same frequency, they should be arranged in the order of their first appearance in the original array. Implement an algorithm with a time complexity of O(n log n) and do not use built-in sorting functions with custom comparators.
Input Format
The first line contains an integer n (1 ≤ n ≤ 10^5) — the number of elements. The second line contains n integers separated by spaces.
Output Format
Output n integers separated by spaces — the sorted array.
Examples
Example 1
INPUT
4
1 2 2 3
OUTPUT
2 2 1 3
Example 2
INPUT
6
1 2 3 4 5 6
OUTPUT
1 2 3 4 5 6
Example 3
INPUT
1
7
OUTPUT
7
main.swift