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
70
71
72
73
74
75
76
77
78
79
#include "bits/stdc++.h"
using namespace std;
using ll = long long;

int const N = 1e7+7, S = 3160, M = 500;
int n, q, cnt[M][S], best[M];
ll mod[M];
bool a[N], isPrime[N];
vector <int> primes, v[M];
set <int> active;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for(int i = 2; i <= n; ++i) isPrime[i] = true;
    for(int i = 2; i*i <= n; ++i)
        if(isPrime[i])
            for(int j = i*i; j <= n; j += i) isPrime[j] = false;
    for(int i = 2; i < S; ++i) 
        if(isPrime[i]){
            primes.push_back(i);
            mod[primes.size()-1] = ((1LL << 40)/i)+1;
            v[primes.size()-1].resize(n/primes.back()+3, 0);
            v[primes.size()-1][0] = primes.back();
        } 
    auto add = [&](int x) -> void{
        a[x] = true;
        active.insert(x);
        for(int i = 0; i < primes.size(); ++i){
            int r = x-((x*mod[i])>>40)*primes[i];
            v[i][cnt[i][r]]--;
            v[i][++cnt[i][r]]++;
            best[i] = max(best[i], cnt[i][r]);
        }
    };
    auto remove = [&](int x) -> void{
        a[x] = false;
        active.erase(x);
        for(int i = 0; i < primes.size(); ++i){
            int r = x-((x*mod[i])>>40)*primes[i];
            v[i][cnt[i][r]]--;
            v[i][--cnt[i][r]]++;
            if(v[i][cnt[i][r]+1] == 0 && best[i] == cnt[i][r]+1) best[i] = cnt[i][r];
        }
    };
    auto update_large = [&](int ans) -> int{
        vector <int> u;
        int p = -1, q = -1;
        for(int x : active){
            if(p != -1 && x-p > 3000 && isPrime[x-p] && 1LL*ans*(x-p) <= n) u.push_back(x-p);
            if(q != -1 && x-q > 3000 && isPrime[x-q] && 1LL*ans*(x-q) <= n) u.push_back(x-q);
            q = p;
            p = x;
        }
        sort(u.begin(), u.end());
        p = -1;
        for(int x : u){
            if(x == p) continue;
            for(int y : active){
                if(1LL*x*ans+y > n) break;
                if(y-x > 0 && a[y-x]) continue;
                int temp = 1, z = x+y;
                for(;z <= n;) temp += a[z], z+=x;
                ans = max(ans, temp);
            }
            p = x;
        }
        return ans;
    };
    for(;q--;){
        int x; cin >> x;
        a[x] ? remove(x) : add(x);
        int ans = 0;
        for(int i = 0; i < primes.size(); ++i) ans = max(ans, best[i]);
        if(ans <= 3333 && active.size() <= 6666) ans = update_large(ans);
        cout << ans << '\n';
        continue;
    }
}