AT_abc329_d [ABC329D] Election Quick Report

题目描述

在由编号为 $1, 2, \ldots, N$ 的 $N$ 名候选人中选出 $1$ 名当选者的选举中，共有 $M$ 张选票。

每张选票都恰好投给一名候选人，第 $i$ 张选票投给了候选人 $A_i$。

现在将按照顺序从第 $1$ 张选票开始依次计票，每计完一张票，都要更新并输出此时如果立即结束计票，谁会当选。

在已计票的选票中，得票数最多的候选人当选。如果有多名候选人得票数相同且并列最多，则编号最小的候选人当选。

对于每个 $i=1,2,\ldots,M$，请你求出只计前 $i$ 张选票时的当选者编号。

输入格式

输入以如下格式从标准输入给出。

$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_M$

输出格式

输出 $M$ 行。

第 $i$ 行输出只计前 $i$ 张选票时的当选者编号。

输入输出样例 #1

输入 #1

3 7
1 2 2 3 1 3 3

输出 #1

1
1
2
2
1
1
3

输入输出样例 #2

输入 #2

100 5
100 90 80 70 60

输出 #2

100
90
80
70
60

输入输出样例 #3

输入 #3

9 8
8 8 2 2 8 8 2 2

输出 #3

8
8
8
2
8
8
8
2

说明/提示

数据范围

• $1 \leq N, M \leq 200000$
• $1 \leq A_i \leq N$
• 输入的所有数均为整数

样例解释 1

用 $C_i$ 表示候选人 $i$ 的得票数。

• 计完第 $1$ 张选票后，$(C_1, C_2, C_3) = (1, 0, 0)$，当选者为 $1$。
• 计完第 $2$ 张选票后，$(C_1, C_2, C_3) = (1, 1, 0)$，当选者为 $1$。
• 计完第 $3$ 张选票后，$(C_1, C_2, C_3) = (1, 2, 0)$，当选者为 $2$。
• 计完第 $4$ 张选票后，$(C_1, C_2, C_3) = (1, 2, 1)$，当选者为 $2$。
• 计完第 $5$ 张选票后，$(C_1, C_2, C_3) = (2, 2, 1)$，当选者为 $1$。
• 计完第 $6$ 张选票后，$(C_1, C_2, C_3) = (2, 2, 2)$，当选者为 $1$。
• 计完第 $7$ 张选票后，$(C_1, C_2, C_3) = (2, 2, 3)$，当选者为 $3$。

由 ChatGPT 4.1 翻译