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
#include <bits/stdc++.h>
using namespace std;            //just some O(q^4) brute

vector<int> smallPrimes = {2, 3, 5, 7, 11, 13};
bool composite(int cur) {
    for(auto p : smallPrimes)
        if(cur%p == 0)
            return true;
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    unordered_map<int, pair<unordered_map<int, int>, int>> db;
    //jumpSize -> {remainderCount, maxOfThose}
    for(auto a : smallPrimes)
        db[a] = {};
    unordered_set<int> used;
    int totalMax = 0;
    
    int n, q;
    cin >> n >> q;
    while(q--) {
        int cur;
        cin >> cur;
        if(used.count(cur) == 0) {          //add
            //add new jump sizes
            for(auto other : used) {
                int diff = abs(other - cur);
                if(diff < 2) {
                    continue;           //jump too small
                }
                if(db.count(diff) != 0) {
                    continue;           //already exists
                }
                if(composite(diff)) {
                    continue;           //jump length already checked by a smallPrime
                }
                
                db[diff] = {};          //add new map
                for(auto i : used) {            //insert everything in there (beside `cur`)
                    db[diff].first[i%diff] += 1;
                    db[diff].second = max(db[diff].second, db[diff].first[i%cur]);
                    totalMax = max(totalMax, db[diff].second);
                }
            }
            used.insert(cur);           //watch out not to add `cur` to db twice
            //alter all sets
            for(const auto &[jump, _] : db) {
                db[jump].first[cur%jump] += 1;
                db[jump].second = max(db[jump].second, db[jump].first[cur%jump]);
                totalMax = max(totalMax, db[jump].second);
            }
        }
        else {          //delete
            used.erase(cur);
            totalMax = 0;
            for(const auto &[jump, _] : db) {
                db[jump].first[cur%jump] -= 1;
                if(db[jump].first[cur%jump] == db[jump].second-1) {         //need to recalculate this max
                    db[jump].second = 0;
                    for(const auto &[_, b] : db[jump].first)
                        db[jump].second = max(db[jump].second, b);
                }
                if(db[jump].first[cur%jump] == 0)           //clear garbage
                    db[jump].first.erase(cur%jump);
                totalMax = max(totalMax, db[jump].second);
            }
        }
        cout << totalMax << "\n";
    }

    return 0;
}