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
69
#include <iostream>
#include <vector>
#include <set>

using namespace std;

struct p {
    int res, q, k;
};

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    vector<bool> v(n + 1), isNotPrime(n + 1);
    vector<int> primes;
    for (long long i = 2; i <= n; ++i) {
        if (!isNotPrime[i]) {
            primes.push_back(i);
            for (long long j = i * i; j <= n; j += i) {
                isNotPrime[j] = 1;
            }
        }
    }

    vector<p> t(n + 1);
    set<int> s;
    int cnt = 0;
    while (q--) {
        int x;
        scanf("%d", &x);
        if (!v[x]) {
            ++cnt;
            v[x] = 1;
            s.insert(x);
        }
        else {
            --cnt;
            v[x] = 0;
            s.erase(x);
        }

        if (!cnt) {
            printf("0\n");
            continue;
        }

        int result = 0;
        int mx = min((n << 1)/cnt, n);
        int it = 0;
        while (it < primes.size() && primes[it] <= mx){
            int k = primes[it];
            ++it;
            for (int j: s) {
                int mod = j % k;
                if (t[mod].q == q && t[mod].k == k){
                    t[mod].res++;
                    result = max(result, t[mod].res);
                } else {
                    t[mod] = {1, q, k};
                    result = max(result, 1);
                }
            }
        }

        printf("%d\n", result);

    }

}