AT_abc329_d [ABC329D] Election Quick Report

[problemUrl]: https://atcoder.jp/contests/abc329/tasks/abc329_d $ 1,\ 2,\ \ldots,\ N $ の番号のついた $ N $ 人の候補者から当選者を $ 1 $ 人選ぶ選挙において、$ M $ 票の投票がありました。 各票ではそれぞれちょうど $ 1 $ 人が投票先として選ばれており、$ i $ 票目の投票先は候補者 $ A_i $ です。 これから $ 1 $ 票目から順に開票を行い、 $ 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 $ 票目のみを開票した場合の当選者の番号を出力せよ。

### 制約 - $ 1\ \leq\ N,M\ \leq\ 200000 $ - $ 1\ \leq\ A_i\ \leq\ N $ - 入力される数値はすべて整数 ### Sample Explanation 1 候補者 $ i $ の得票数を $ C_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 $ です。