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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <bits/stdc++.h>
using namespace std;
using ind = long long;
using cind = const ind;
#define FOR(i,l,r) for(ind i = (l); i <= (r); i++)
#define FORD(i,l,r) for(ind i = (l); i >= (r); i--)

constexpr ind PRIMES = 168;
constexpr ind primes[168]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};
bitset<10'000'001> kamienie(0);
vector<vector<ind>> p;
ind amounts_got[1'000'002];


ind max_k_q[1'000'001];
ind q[1'000'001];
ind probability[1'000'001];
mt19937_64 rng_core(20260329);
vector<ind> all_kamienie1;
map<ind,ind> all_kamienie2;
ind random_kamien(){
    return all_kamienie1[rng_core()%all_kamienie1.size()];
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cind P_MAX = 3'333;
    bitset<P_MAX+1> is_prime(0);
    vector<ind> larger_primes;
    is_prime.flip();
    is_prime[0]=0;
    is_prime[1]=0;
    FOR(i,2,P_MAX) if(is_prime[i]) {
        for(ind j = i; j <= P_MAX; j += i) is_prime[j]=0;
        if(primes[167] < i) larger_primes.push_back(i);
    }
    p.resize(PRIMES);
    FOR(i,0,PRIMES-1){
        p[i].resize(primes[i]);
        for(auto& k : p[i]) {k = 0; amounts_got[0]++;}
    }
    ind N, Q;
    cin >> N >> Q;
    ind max_k=0;
    FOR(qi,1,Q) cin >> q[qi];

    ind kamienie_amount=0;
    FOR(qi,1,Q){
        ind pos = q[qi];
        if(N > 1000){
            if(kamienie[pos] == 0){
                all_kamienie1.push_back(pos);
                all_kamienie2[pos] = all_kamienie1.size() - 1;
            }else{
                all_kamienie2[all_kamienie1.back()] = all_kamienie2[pos];
                all_kamienie1[all_kamienie2[pos]] = all_kamienie1.back();
                all_kamienie1.pop_back();
                all_kamienie2.erase(pos);
            }
        }
        kamienie_amount++;
        if(kamienie[pos] == 1) kamienie_amount -= 2;
        if(kamienie[pos] == 0)
            FOR(prime_i,0,PRIMES-1) {
                ind& p2 = p[prime_i][pos%primes[prime_i]];
                amounts_got[p2]--;
                p2++;
                amounts_got[p2]++;
            }
        if(kamienie[pos] == 1)
            FOR(prime_i,0,PRIMES-1){
                ind& p2 = p[prime_i][pos%primes[prime_i]];
                amounts_got[p2]--;
                p2--;
                amounts_got[p2]++;
            }
        kamienie[pos] = 1 - kamienie[pos];
        if(amounts_got[max_k+1] > 0) max_k++;
        else if(amounts_got[max_k] == 0) max_k--;

        if((2 <= kamienie_amount) and (kamienie_amount <= 10'000) and (N > 1000)){
            ind end_qi = qi + all_kamienie1.size()/3;
            if(end_qi > Q) end_qi = Q;
            while(probability[qi] < 1'000'000'000){
                ind A = random_kamien();
                ind B = random_kamien();
                while(A == B){
                    A = random_kamien();
                    B = random_kamien();
                }
                ind C = max(A,B) - min(A,B);
                for(auto k : primes) while(C%k == 0 and C > 1'000) C/=k;
                vector<ind> d;
                for(auto k : larger_primes) while(C%k == 0) {C/=k; d.push_back(k);}
                for(auto d1 : d){
                    ind R = A%d1;
                    ind wyn=0;
                    for(auto k : all_kamienie1) if(k%d1 == R) wyn++;
                    max_k_q[qi] = max(max_k_q[qi], wyn);
                    ind gain=8'200'000;
                    if(d.size() == 2) gain /= 2;
                    probability[qi]+=gain;
                    ind c1= (gain/all_kamienie1.size())*(5/6);
                    stack<ind> changes;
                    FOR(qj,qi+1,end_qi){
                        if(q[qj]%d1 == R){
                            wyn++;
                            if(kamienie[q[qj]] == 1) wyn -= 2;
                            kamienie[q[qj]] = 1 - kamienie[q[qj]];
                            changes.push(q[qj]);
                        }
                        gain -= c1;
                        max_k_q[qj] = max(max_k_q[qj],wyn);
                        probability[qj] += gain;
                    }
                    while(changes.size()>0){
                        kamienie[changes.top()] = 1 - kamienie[changes.top()];
                        changes.pop();
                    }
                }
                if(d.size()==0){
                    ind gain=8'200'000;
                    probability[qi]+=gain;
                    ind c1= (gain/all_kamienie1.size())*(5/6);
                    FOR(qj,qi+1,end_qi){
                        gain -= c1;
                        probability[qj] += gain;
                    }
                }
            }
        }
        cout << max(max_k,max_k_q[qi]) << '\n';
    }
}