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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
#define nl '\n'

using namespace std;
const int flip_count = 80*80;
const int MAXN = 1e7+1;
const int SQRT = 3164;

int sieve[MAXN];
vector<int> counts[SQRT];
bitset<MAXN> bits;
vector<int> vals;
unordered_map<int, int> inds;

int randint(int a, int b){
    static mt19937_64 mt(937684423);
    return mt()%(b-a+1)+a;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    cin>>n>>q;
    vector<int> primes;
    for(int i=2; i<MAXN; i++){
        if(!sieve[i]){
            if(i < SQRT){
                primes.push_back(i);
            }
            for(int j=i; j<MAXN; j+=i){
                sieve[j] = i;
            }
        }
    }
    //cerr<<primes.size()<<nl;
    for(auto p: primes){
        counts[p].assign(p, 0);
    }
    for(int h=1; h<=q; h++){
        //cerr<<h<<nl;
        int val;
        cin>>val;
        if(bits[val]){
            bits[val] = 0;
            inds[vals.back()] = inds[val];
            swap(vals.back(), vals[inds[val]]);
            vals.pop_back();
            inds.erase(val);
            for(auto p: primes){
                counts[p][val%p]--;
            }
        }else{
            bits[val] = 1;
            vals.push_back(val);
            inds[val] = vals.size()-1;
            for(auto p: primes){
                counts[p][val%p]++;
            }
        }
        int res = 0;
        if(vals.size() == 1){ cout<<1<<nl; continue; }
        set<pair<int, int>> flipped;
        for(int i=0; i<min(flip_count,(int)vals.size()*((int)vals.size()-1)/2); i++){
            int ind1, ind2;
            do{
                ind1 = randint(0, vals.size()-1);
                ind2 = randint(0, vals.size()-1);
            }while(ind1 == ind2 || flipped.count({min(ind1, ind2), max(ind1, ind2)}));
            int x = vals[ind1], y = vals[ind2];
            flipped.insert({min(ind1, ind2), max(ind1, ind2)});
            //cerr<<x<<' '<<y<<nl;
            vector<int> facted;
            if(x < y) swap(x, y);
            int d = x - y;
            while(d > 1){
                if(facted.empty() || facted.back() == sieve[d]){
                    facted.push_back(sieve[d]);
                }
                d /= sieve[d];
            }
            for(auto p: facted){
                //cerr<<p<<nl;
                if(p <= SQRT){
                    res = max(res, counts[p][x%p]);
                }else{
                    int cnt = 0;
                    for(int j=x%p; j<=MAXN; j+=p){
                        cnt += bits[j];
                    }
                    res = max(res, cnt);
                }
            }
        }
        //assert(res >= vals.size()/2);
        cout<<res<<nl;
    }
    return 0;
}