重要な性質として、以下が成り立ちます。

• \(i+1\) 票目までを開票した場合に当選する候補者は、\(i\) 票目までを開票した場合に当選する候補者あるいは \(i+1\) 票目の投票先となった候補者に限られる。

この性質を利用すると、各候補者の得票数および \(i\) 票目までを開票した場合に当選する候補者を管理しておき、その候補者と \(i+1\) 票目の投票先となった候補者の得票数を比較しながら、\(i = 1, 2, \ldots, N\) の順に \(i\) 票目までを開票した場合に当選する候補者を更新していくことで答えを求めることができます。

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> a(m);
	for (int i = 0; i < m; i++) cin >> a[i];
	vector<int> cnt(n + 1); // 各候補者の得票数
	int ans = 0; // 現時点での当選者
	for (int i = 0; i < m; i++) {
		cnt[a[i]]++;
		if (cnt[ans] < cnt[a[i]]) ans = a[i];
		else if (cnt[ans] == cnt[a[i]]) ans = min(ans, a[i]);
		cout << ans << '\n';
	}
}