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
#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e7+5,M=1e6+5,B=6;

#define gc getchar_unlocked
#define pc putchar_unlocked
inline int read(){
    int x=0; char c=gc();
    while(!isdigit(c))c=gc();
    while(isdigit(c))x=x*10+c-'0',c=gc();
    return x;
}
void write(const int x){
    if(x>9)write(x/10);
    pc(x%10+'0');
}

int notp[N],mind[N],prime[N],cprime;
void init(int n){
    for(int i=2;i<=n;i++){
        if(!notp[i])prime[++cprime]=i,mind[i]=i;
        for(int j=1,x;;j++){
            x=i*prime[j];
            if(x>n)break;
            notp[x]=1;
            mind[x]=prime[j];
            if(i%prime[j]==0)break;
        }
    }
}

int n,q;
int qt[M],qx[M],ans[M];
set<int> s;
int val[M],cval;
int cnt[N],que[N],cque;

void solve(int L,int R){
    // fprintf(stderr,"solve [%d, %d]\n",L,R);
    cval=cque=0;
    for(int i:s)val[cval++]=i;
    int m=max(1,(int)s.size()/B);
    for(int l=0,r;l<cval;l=r){
        r=l+B;
        if(r+B>cval)r=cval;
        for(int i=l;i<r;i++)for(int j=i+1;j<r;j++){
            int x=val[j]-val[i];
            while(x>1){
                int p=mind[x];
                while(x%p==0)x/=p;
                if(!cnt[p])que[cque++]=p;
                cnt[p]++;
            }
        }
    }
    for(int i=0;i<cque;i++){
        const int p=que[i];
        // fprintf(stderr,"cnt[%d] = %d\n",p,cnt[p]);
        if(exchange(cnt[p],0)<m)continue;
        static int c[N],cc[N];
        int maxn=0;
        cc[0]=1e9;
        auto ins=[&](int x){
            // fprintf(stderr,"ins %d\n",x);
            x%=p;
            cc[c[x]]--,c[x]++,cc[c[x]]++;
            maxn=max(maxn,c[x]);
        };
        auto del=[&](int x){
            x%=p;
            // fprintf(stderr,"del %d\n",x);
            cc[c[x]]--,c[x]--,cc[c[x]]++;
            if(!cc[maxn])maxn--;
        };
        for(int i=0;i<cval;i++)ins(val[i]);
        for(int i=L;i<R;i++){
            if(qt[i])ins(qx[i]);
            else del(qx[i]);
            ans[i]=max(ans[i],maxn);
            // fprintf(stderr,"qid = %d, maxn = %d\n",i,maxn);
        }
        for(int i=0,x;i<cval;i++)x=val[i]%p,cc[c[x]]=0,c[x]=0;
        for(int i=L,x;i<R;i++)x=qx[i]%p,cc[c[x]]=0,c[x]=0;
    }
    for(int i=L;i<R;i++){
        if(qt[i])s.insert(qx[i]);
        else s.erase(qx[i]);
        ans[i]=max(ans[i],((int)s.size()+1)/2);
        if(s.size()>3)continue;
        vector<int> a(s.begin(),s.end());
        if(s.size()==2&&a[1]-a[0]!=1)ans[i]=max(ans[i],2);
        if(s.size()==3)ans[i]=max(ans[i],gcd(a[2]-a[1],a[1]-a[0])>1?3:2);
    }
}

int main(){
    init(1e7);
    n=read(),q=read();
    for(int i=0;i<q;i++){
        qx[i]=read();
        if(s.count(qx[i]))s.erase(qx[i]);
        else qt[i]=1,s.insert(qx[i]);
    }
    s.clear();
    for(int l=0,r;l<q;l=r){
        r=min(q,l+max(1,(int)s.size()/5));
        solve(l,r);
    }
    for(int i=0;i<q;i++)write(ans[i]),pc('\n');
    return 0;
}