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
#pragma GCC optimize(2, 3, "Ofast", "inline", "unroll-loops")
#include <bits/stdc++.h>
using ll = int;
using ld = long double;
using ull = unsigned long long;
using namespace std;
template <class T>
using Ve = vector<T>;
#define ALL(v) (v).begin(), (v).end()
#define pii pair<ll, ll>
#define rep(i, a, b) for(ll i = (a); i <= (b); ++i)
#define per(i, a, b) for(ll i = (a); i >= (b); --i)
#define pb push_back
bool Mbe;
ll read() {
    ll x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
void write(ll x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
const ll N = 1e7 + 9, B = 2e2;
ll n, q, bin[N], ans1, ans, pr[N], prc, mnp[N];
bool vis[N];
ll tim[N], cc[N];
ll td[N], cd[N], vd[10009], lend;
ll cnt[B + 5][30009], a[10009], len;
set<ll> S;
mt19937 rnd(time(0));
void Init(ll n) {
    rep(i, 2, n) {
        if(!vis[i]) pr[++prc] = i, mnp[i] = prc;
        rep(j, 1, prc) {
            if(pr[j] * i > n) break;
            vis[pr[j] * i] = 1, mnp[pr[j] * i] = j;
            if(i % pr[j] == 0) break;
        }
    }
    cerr << pr[B + 1] << "\n";
}
bool Med;
int main() {
    // freopen("B2.in", "r", stdin);
    // freopen("B2.out", "w", stdout);
    cerr << fabs(&Med - &Mbe) / 1048576.0 << "MB\n";
    n = read(), q = read();
    Init(1e7);
    rep(qid, 1, q) {
        // if(qid % 10000 == 0) cerr << qid << endl;
        ll x = read();
        if(!S.count(x)) {
            S.insert(x);
            rep(i, 1, B) {
                ll md = x % pr[i];
                bin[cnt[i][md]]--;
                cnt[i][md]++, ans1 = max(ans1, cnt[i][md]);
                bin[cnt[i][md]]++;
            }
        }
        else {
            S.erase(x);
            rep(i, 1, B) {
                ll md = x % pr[i];
                bin[cnt[i][md]]--;
                cnt[i][md]--;
                bin[cnt[i][md]]++;
            }
            while(ans1 && !bin[ans1]) --ans1;
        }
        ans = ans1;
        ll p = pr[B + 1];
        if((n + p - 1) / p <= ans) {
            write(ans), putchar('\n');
            continue;
        }
        len = 0;
        for(ll x : S) a[++len] = x;
        if(!len) {
            puts("0");
            continue;
        }
        Ve<ll> vec, chk;
        rep(i, 1, 10) vec.pb(a[rnd() % len + 1]);
        sort(ALL(vec)), vec.resize(unique(ALL(vec)) - vec.begin());
        lend = 0;
        ll md = 0;
        rep(i, 0, (ll)vec.size() - 1) {
            rep(j, i + 1, (ll)vec.size() - 1) {
                ll d = vec[j] - vec[i];
                while(d > 1) {
                    ll mn = mnp[d];
                    d /= pr[mn];
                    if(mn > B) {
                        if(td[mn] != qid) td[mn] = qid, cd[mn] = 0, vd[++lend] = mn;
                        cd[mn]++, md = max(md, cd[mn]);
                    }
                }
            }
        }
        ll cnt = 0;
        rep(j, 1, lend) cnt += (cd[vd[j]] == md);
        if(len <= 10 || cnt == 1) {
            rep(j, 1, lend) {
                ll p = vd[j];
                if(md != cd[p]) continue;
                if((n + p - 1) / p <= ans) break;
                rep(i, 1, len) {
                    ll v = i % p;
                    if(tim[v] != p || j == 0) tim[v] = p, cc[v] = 0;
                    ++cc[v], ans = max(ans, cc[v]);
                }
            }
        }
        write(ans), putchar('\n');
    }
    cerr << "\n" << clock() * 1.0 / CLOCKS_PER_SEC * 1000 << "ms\n";
    return 0;
}