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
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll Wsqrt = 1e7+10;
vector<ll> cnt(Wsqrt);

ll solve1(vector<ll> &a, ll k) {
    ll res = 1;
    for(auto x : a) {
        cnt[x%k]++;
        res = max(res, cnt[x%k]);
    }
    for(auto x : a) {
        cnt[x%k] = 0;
    }
    return res;
}

mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
ll gn(ll a, ll b) {
	uniform_int_distribution dist(a,b);
	return dist(rng); 
}

vector<ll> spf;

void build_spf(ll N) {
    spf.resize(N+1);
    for(ll i=0; i<=N; i++) spf[i] = i;
    for(ll i=2; i*i <= N; i++) {
        if(spf[i]==i) {
            for(ll j = i*i; j <= N; j += i) {
                if(spf[j] == j) spf[j] = i;
            }
        }
    }
}

vector<ll> get_primes(ll x) {
    vector<ll> res;
    while(x > 1) {
        ll p = spf[x];
        res.push_back(p);
        while(x%p == 0) x /= p;
    }
    return res;
}

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

	ll n, q;
	cin >> n >> q;
	build_spf(n);
	vector<ll> on(n+1);
	vector<ll> a;
	while(q--) {
		ll x; cin >> x;
		if(on[x]) {
			a.erase(remove(a.begin(), a.end(), x), a.end());
		} else a.push_back(x);
		on[x] ^= 1;
		ll C = 10;
		ll ans = (a.size()+1) / 2;
		for(ll t=0; t<C; ++t) {
			ll i = gn(0,a.size()-1);
			ll j = gn(0,a.size()-1);
			for(auto d : get_primes(abs(a[i]-a[j]))) ans = max(ans, solve1(a,d));
		}
		cout << ans << "\n";
	}

	return 0;
}