题目描述

某系统记录了一段长度为 $n$ 的正整数序列，第 $i$ 个数字为 $a_i$。

现在需要按照每个数字在整个序列中的出现次数，对所有元素重新排列。

具体排序规则如下：

• 出现次数较多的数字排在出现次数较少的数字前面；
• 如果两个位置上的数字在整个序列中的出现次数相同，则它们之间的相对顺序保持不变。

也就是说，对于原序列中的两个位置 $i<j$：

• 若 $a_i$ 的出现次数大于 $a_j$ 的出现次数，则排序后 $a_i$ 应排在 $a_j$ 前面；
• 若二者出现次数相同，则排序后 $a_i$ 仍排在 $a_j$ 前面。

请输出按照上述规则整理后的完整序列。

输入格式

第一行输入一个正整数 $n$，表示序列中数字的数量。

第二行输入 $n$ 个正整数 $a_i$，表示原始序列。

输出格式

输出一行 $n$ 个正整数，表示按照规则排序后的序列。

6
1 2 1 2 2 1

1 2 1 2 2 1

样例 1 解释

由于 $1$ 和 $2$ 的出现次数相同，因此相对顺序不变。

7
2 3 1 1 3 2 1

1 1 1 2 3 3 2

样例 2 解释

由于 $1$ 的出现次数比 $2$ 和 $3$ 多，因此 $1$ 会被排在 $2$ 和 $3$ 前面。$2\ 3$ 由于出现次数相同，因此相对位置不变。

数据范围

对于所有数据，$1\le n\le 5\times 10^5$，$1\le a_i\le 10^9$。每个测试点的具体限制见下表：