← 返回题目列表

AtCoder · abc329_d

G. 选举快速报告

中文机器翻译题面 查看原题

分数: 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