1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//Solution by Mikołaj Kołek

#include "bits/stdc++.h"
#define intin *istream_iterator<int>(cin)

using namespace std;

vector<pair<int, unordered_map<int, int>>> primesLessThan(int num) {
	vector<bool> isPrime(num, true);
	for(int i = 2; (i * i) < num; i++)
		if(isPrime[i])
			for(int j = (i * i); j < num; j += i)
				isPrime[j] = false;
	
	vector<pair<int, unordered_map<int, int>>> primes;
	for(int i = 2; i < num; i++)
		if(isPrime[i])
			primes.push_back({ i, {} });
	
	return primes;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n = intin, q = intin;
	auto primes = primesLessThan(n);
	
	map<int, int> counts = { { 0, n } };
	vector<bool> stones(n);
	while(q--) {
		int request = intin - 1;
		stones[request] = stones[request] ^ 1;
		
		if(stones[request]) {
			for(auto &[prime, storage] : primes) {
				int before = storage[request % prime];
				if(counts[before] == 1)
					counts.erase(before);
				else
					counts[before]--;
				
				storage[request % prime]++;
				counts[before + 1]++;
			}
		}
		else {
			for(auto &[prime, storage] : primes) {
				int before = storage[request % prime];
				if(counts[before] == 1)
					counts.erase(before);
				else
					counts[before]--;
				
				if(before > 1)
					storage[request % prime]--;
				else
					storage.erase(request % prime);
				counts[before - 1]++;
			}
		}
		
		cout << counts.rbegin()->first << "\n";
	}
		
	return 0;
}