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
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
const int MX=1000100,INF=100*MX,MP=670670;
int n,m,q,pr,tot,ans,pos,cp[2],p[MP],a[MX],all[MX],w[MX],c[MX],cnt[MX],mn[MX],st[MX],b[MX];
unordered_map<int,int> mps[MP];
bool u[10*MX];
int main() {
  scanf("%d%d",&n,&q);
  for (int i=2; i<=n; i++) if (!u[i]) {
    p[pr++]=i;
    for (int j=i+i; j<=n; j+=i) u[j]=true;
  }
  for (int i=1; i<=q; i++) {
    scanf("%d",&a[i]);
    all[tot++]=a[i];
  }
  sort(all,all+tot);
  tot=unique(all,all+tot)-all;
  for (int i=1; i<=q; i++) {
    int val=a[i];
    a[i]=lower_bound(all,all+tot,a[i])-all+1;
    if (pos=w[a[i]]) {
      --cp[val&1];
      int l=1,r=m;
      while (l<r) {
        int mid=(l+r)/2;
        if (st[mid]>=pos) r=mid; else l=mid+1;
      }
      mn[i]=mn[pos]=c[st[r]];
      w[a[i]]=0;
    } else {
      ++cp[val&1];
      w[a[i]]=i;
    }
    cnt[i]=cp[0]+cp[1];
    if (cnt[i]<=2) c[i]=INF; else c[i]=max(cp[0],cp[1]);
    while (m>0 && c[i]<=c[st[m]]) --m;
    st[++m]=i;
  }
  for (int i=1; i<=q; i++) if (mn[i]==0) {
    int l=1,r=m;
    while (l<r) {
      int mid=(l+r)/2;
      if (st[mid]>=i) r=mid; else l=mid+1;
    }
    mn[i]=c[st[r]];
  }
  //for (int i=1; i<=q; i++) printf("%d: %d %d %d\n",i,mn[i],cnt[i],c[i]);
  for (int i=1; i<=tot; i++) w[i]=0;
  for (int i=1; i<=q; i++) {
    if (pos=w[a[i]]) {
      if (mn[pos]<INF) {
        int lim=(n-1)/mn[pos];
        for (int j=0; j<pr && p[j]<=lim; j++) {
          int rst=all[a[i]-1]%p[j];
          auto it=mps[j].find(rst);
          --b[it->second];
          if (it->second==ans && b[it->second]==0) --ans;
          --it->second;
          ++b[it->second];
        }
      }
      w[a[i]]=0;
    } else {
      w[a[i]]=i;
      if (mn[i]<INF) {
        int lim=(n-1)/mn[i];
        for (int j=0; j<pr && p[j]<=lim; j++) {
          int rst=all[a[i]-1]%p[j];
          //printf("add %d %d\n",p[j],rst);
          auto it=mps[j].find(rst);
          if (it==mps[j].end()) {
            mps[j][rst]=1;
            ans=max(ans,1);
          } else {
            --b[it->second];
            ++it->second;
            ++b[it->second];
            ans=max(ans,it->second);
          }
        }
      }
    }
    if (cnt[i]<=2) printf("%d\n",cnt[i]); else printf("%d\n",max(c[i],ans));
  } 
  return 0;
}