选举速报

题目描述

有编号为 $1, 2, \ldots, N$ 的 $N$ 名候选人参加的一场选举中,投出了 $M$ 票。

每票都恰好投给 $1$ 名候选人,第 $i$ 票投给候选人 $A_i$。

接下来按顺序从第 $1$ 票开始计票,每计完一票,就更新并显示该时点开票结束时的当选者。

在已开票的票中,得票数最多的候选人当选。不过,得票数最多的候选人有多个时,其中编号最小的候选人当选。

对每个 $i = 1, 2, \ldots, M$,求出只开第 $1, 2, \ldots, i$ 票时的当选者。

输入格式

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

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

输出格式

输出 $M$ 行。

第 $i$ 行输出只开第 $1, 2, \ldots, i$ 票时的当选者编号。

样例

3 7
1 2 2 3 1 3 3

1
1
2
2
1
1
3

用 $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$。

100 5
100 90 80 70 60

100
90
80
70
60

9 8
8 8 2 2 8 8 2 2

8
8
8
2
8
8
8
2

数据范围

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