Sorting by frequency while preserving order

Rust Hard sorting

Task «Sorting by frequency while preserving order»

Given an array of integers, it is necessary to sort it in descending order of the frequency of occurrence of elements. If two elements occur the same number of times, they should be arranged in the order of their first appearance in the original array. It is required to implement a sorting algorithm with a time complexity of O(n log n) and using additional memory of O(n).

Input Format

The first line contains an integer n (1 ≤ n ≤ 10^5). The second line contains n integers separated by spaces.

Output Format

Output n integers separated by spaces — the sorted array.

Examples

Example 1

INPUT

3
3 2 1

OUTPUT

3 2 1

main.rs