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
#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define int long long
#define ld long double
#define pb push_back

using namespace std;
#define rg ranges

constexpr int TRIALS = 12;

vector<int> sieve;

void sift(int n) {
    for(int i = 2; i * i <= n; i++) if(!sieve[i]) {
        for(int j = i * i; j <= n; j += i) sieve[j] = i;
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, q;
    cin >> n >> q;
    //int squirt = (int)sqrt(n);
    //int squirt = 9120;
    int squirt = (int)(2 * sqrt((ld)n * log(8)));
    DC << "squirt = " << squirt << '\n';
    squirt = min(squirt, max(1ll, n - 1));
    mt19937 rnd(squirt * 2137 + q - n * 67);
    sieve.resize(n + 1);
    sift(n);
    unordered_map<int, pair<vector<int>, set<pair<int, int>>>> mp;
    rep(i, 2, squirt + 1) if(!sieve[i]) {
        set<pair<int, int>> s;
        rep(j, 0, i) s.insert({0, j});
        vector<int> v(i);
        mp[i] = {v, s};
    }
    unordered_set<int> inS;
    // O(q * (n * TRIALS/squirt + squirt / ln(2)))
    // 12e7 / x + x / ln(2)
    while(q--) {
        int x;
        cin >> x;
        int ans = 0;
        repIn2(prm, vs, mp) {
            // O(q * mp.size() * log2(squirt)) = O(q * squirt/ln(squirt) * log2(squirt)) = O(q * squirt / ln(2))
            auto& [v, s] = vs;
            auto rem = x % prm;
            s.erase({(inS.count(x) ? v[rem]-- : v[rem]++), rem});
            s.insert({v[rem], rem});
            ans = max(ans, s.rbegin() -> first);
        }
        if(inS.count(x)) inS.erase(x);
        else inS.insert(x);
        if(inS.size() && (2 * n > (int)inS.size() * squirt + 15)) {
            // O(q * (n/squirt) * TRIALS)
            vector<int> v;
            repIn(i, inS) v.pb(i);
            rep(_, 0, TRIALS) {
                auto S = v[rnd() % (v.size())];
                unordered_map<int, int> mp2;
                repIn(i, v) if(i != S) {
                    unordered_set<int> pfs;
                    int tmp = abs(i - S);
                    while(sieve[tmp]) {
                        pfs.insert(sieve[tmp]);
                        tmp /= sieve[tmp];
                    }
                    if(tmp != 1) pfs.insert(tmp);
                    repIn(j, pfs) mp2[j]++;
                }
                int mAns = 0;
                repIn2(pf, cn, mp2) mAns = max(mAns, cn);
                ans = max(ans, mAns + 1);
            }
        }
        cout << ans << '\n';
    }
}