Sorting by frequency and value

Python Medium sorting

Task «Sorting by frequency and value»

Given an array of integers. Sort it in descending order of the frequency of occurrence of elements. If two elements occur the same number of times, then they are sorted in ascending order of value. It is guaranteed that the length of the array does not exceed 10^5, and the values of the elements are in the range from -10^9 to 10^9.

Input Format

The first line contains an integer n — the number of elements in the array. The second line contains n integers separated by spaces.

Output Format

Output n numbers separated by spaces — the array sorted according to the rules.

Examples

Example 1

INPUT

6
5 3 5 1 2 3

OUTPUT

3 3 5 5 1 2

Example 2

INPUT

5
1 2 3 4 5

OUTPUT

1 2 3 4 5

Example 3

INPUT

4
1 1 1 1

OUTPUT

1 1 1 1

Example 4

INPUT

7
9 8 7 6 5 4 3

OUTPUT

3 4 5 6 7 8 9

main.py