分数: 350 点
问题陈述
进行一次选举,从中选出一名获胜者 N 考生编号 1, 2, \ldots, N,并且已经有 M 投票。
每张选票都只投给一位候选人, i第 1 票投给候选人 A_i.
票数将按照从先到后的顺序进行计票,每次计票后,都会更新并显示当前的获胜者。
在计票的候选人中得票最多的候选人是获胜者。如果有多位候选人得票最多,则候选人数最少的获胜者。
对于每个 i = 1, 2, \ldots, M,仅计算第一名时确定获胜者 i 投票。
约束
- 1 \leq N, M \leq 200000
- 1 \leq A_i \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \ldots A_M
输出
打印 M 行。
的 i- 仅计算第一行时应包含获胜者的候选人编号 i 投票。
示例输入 1
3 7 1 2 2 3 1 3 3
示例输出 1
1 1 2 2 1 1 3
让 C_i 表示候选人的票数 i.
- 第一票计票后, (C_1, C_2, C_3) = (1, 0, 0),所以获胜者是 1.
- 第二次投票统计后, (C_1, C_2, C_3) = (1, 1, 0),所以获胜者是 1.
- 第三次投票统计后, (C_1, C_2, C_3) = (1, 2, 0),所以获胜者是 2.
- 第四票清点后, (C_1, C_2, C_3) = (1, 2, 1),所以获胜者是 2.
- 第五票统计后, (C_1, C_2, C_3) = (2, 2, 1),所以获胜者是 1.
- 第六票统计后, (C_1, C_2, C_3) = (2, 2, 2),所以获胜者是 1.
- 第七票统计后, (C_1, C_2, C_3) = (2, 2, 3),所以获胜者是 3.
示例输入 2
100 5 100 90 80 70 60
示例输出 2
100 90 80 70 60
示例输入 3
9 8 8 8 2 2 8 8 2 2
示例输出 3
8 8 8 2 8 8 8 2