背景

2025 年河南省青少年程序设计能力认证 第二轮认证（小学组） 第三题

PDF 首页注意事项：输入文件中可能存在行末空格，请选手使用更完善的读入方式（例如 scanf 函数）避免出错。

题目描述

给定 $n\ (1\le n\le 5\times 10^5)$ 个正整数，第 $i$ 个数字为 $a_i\ (1\le a_i\le 10^9)$。请对他们进行排序。

其中排序 $a_i$ 和 $a_j$（$i<j$）的规则为：如果 $a_i$ 这个数字出现次数和 $a_j$ 的出现次数相同，则 $a_i$ 排在前面。否则把出现次数多的排在前面。

输入格式

第一行一个正整数 $n$ 表示要排序的数字数量。

接下来一行 $n$ 个正整数表示要排序的数字 $a_i$。

输出格式

输出一行 $n$ 个正整数表示排序后的数字。

6
1 2 1 2 2 1

1 2 1 2 2 1

7
2 3 1 1 3 2 1

1 1 1 2 3 3 2

提示

【样例解释 #1】

由于 $1$ 和 $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$。每个测试点的具体限制见下表：

::cute-table{tuack} | 测试点编号 | 约束 | | :--: | :--: | | $1$ | 每个数字只出现一次 | | $2\sim 3$ | $n=5$ 且只有两种数字 | | $4\sim 7$ | $n\le 100$ | | $8\sim 11$ | $a_i\le 10^6$ | | $12\sim 20$ | 没有其他限制 |