#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define INF 1000000001LL
#define POT (1LL<<23)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define vvi vector<vi>
#define al(x) x.begin(),x.end()
#define rev(x) reverse(al(x))
#define X 18
#define K 100
#define FCTCST 7
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U,typename Z>
pair<T, U> operator*(const pair<T, U>& a, const Z& b) {
    return {a.first*b, a.second*b};
}
template<typename T, typename U,typename Z>
pair<T, U> operator/(const pair<T, U>& a, const Z& b) {
    return {a.first/b, a.second/b};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os<<"{"<<p.ff<<", "<<p.ss<<"}";
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i) os << ", ";
        os << v[i];
    }
    os << "}";
    return os;
}
template<ll MOD=998244353>
struct mint_t{
    ll x;
    mint_t(ll y=0){x=y%MOD;if(x<0)x+=MOD;}
    mint_t& operator+=(const mint_t& a){if((x+=a.x)>=MOD)x-=MOD;return *this;}
    mint_t& operator-=(const mint_t& a){if((x+=MOD-a.x)>=MOD)x-=MOD;return *this;}
    mint_t operator+(const mint_t& a)const{mint_t res(*this);return res+=a;}
    mint_t operator-(const mint_t& a)const{mint_t res(*this);return res-=a;}
    mint_t& operator*=(const mint_t& a){(x*=a.x)%=MOD;return *this;}
    mint_t operator*(const mint_t& a)const{mint_t res(*this);return res*=a;}
    mint_t fp(ll y)const{
        mint_t a=1,b=x;
        if(y<0)y+=MOD-1;
        while(y){
            if(y&1)a*=b;
            b*=b;
            y/=2;
        }
        return a;
    }
    mint_t& operator/=(const mint_t& a){(*this)*=a.fp(MOD-2);return *this;}
    mint_t operator/(const mint_t& a)const{mint_t res(*this);return res/=a;}
};
template<ll MOD>
ostream& operator<<(ostream& os, const mint_t<MOD>& m){
    return os << m.x;
}
#define mint mint_t<>
template<long long MOD>
istream& operator>>(istream& in, mint_t<MOD>& a){
    ll x;
    in>>x;
    a=mint_t<MOD>(x);
    return in;
}
template<long long MOD>
istream& operator<<(istream& out, mint_t<MOD>& a){
    out<<a.x;
    return out;
}
mint fct[FCTCST];
mint bnm(ll a,ll b){
    if(b>a || a<0)return 0;
    return fct[a]/fct[b]/fct[a-b];
}
#define LM 10000007
ll n,q,a;
bool cz[LM];
ll pm[LM];
unordered_map<ll,ll> il[1000007];
ll il2[1000007];
ll dz[LM];
ll kied[10000007];
bool typ[1000007];
ll id[LM];
mt19937_64 mt(2137);
vi prm;
void solve(){
    for(ll i=2;i<LM;i++)dz[i]=i;
    for(ll i=2;i<LM;i++){
        if(dz[i]==i){prm.pb(i);id[i]=prm.size()-1;}
        for(ll j=0;j<prm.size();j++){
            if(prm[j]*i>=LM)break;
            dz[prm[j]*i]=prm[j];
            if(prm[j]==dz[i])break;
        }
    }
    vi zap;
    cin>>n>>q;
    for(ll i=0;i<q;i++){
        cin>>a;
        zap.pb(a);
        
    }
    unordered_set<ll>s;
    unordered_set<ll>s2;
    vi old;
    ll dd=-1,ds=-1;
    ll pp=-1;
    vi rozw;
    for(ll i=0;i<q;i++){
        a=zap[i];
        
        if(s.find(a)==s.end()){
            dd--;
            s.insert(a);
        }
        else{
            ds--;
            s.erase(a);
            s2.erase(a);
        }
        if(dd==-1 || ds==-1){
            dd=s.size()/3;ds=s.size()/4;
            s2=s;
            old.clear();for(ll j:s)old.pb(j);
        }
        rozw.pb(a);
        if(dd==0 || ds==0 || i==q-1){
            if(old.empty()){
                cz[rozw[0]]^=1;
                cout<<"0\n";
                rozw.clear();
                dd=-1;
                ds=-1;
                continue;
            }
            vi pm;
            vi pol;
            for(ll j:s2)pm.pb(j);
            unordered_map<ll,ll>mp;
            ll C=20*rozw.size();
            if(old.size()>1)
            for(ll j=0;j<C;j++){
                ll p1=0,p2=0;
                while(p1==p2){p1=mt()%pm.size();p2=mt()%pm.size();}
                ll x=abs(pm[p1]-pm[p2]);
                assert(x);
                while(x!=1){
                    ll y=dz[x];
                    mp[y]++;
                    while(x%y==0)x/=y;
                }
            }
            for(pii j:mp){
                if(j.ss>=C/20)pol.pb(id[j.ff]);
            }
            //cout<<rozw<<" "<<pol<<" "<<old <<endl;
            ll ak=old.size()+1;
            il2[1]=1;
            for(ll k:old){
                for(ll j:pol){
                    il2[il[j][k%prm[j]]]--;
                    il2[++il[j][k%prm[j]]]++;
                }
            }
            while(!il2[ak])ak--;
            cout<<ak<<"\n";
            cz[rozw[0]]^=1;
            for(ll k=1;k<rozw.size();k++){
                a=rozw[k];
               //    cout<<a<<" ";
                if(cz[a]){
                    for(ll j:pol){
                        il2[il[j][a%prm[j]]]--;
                        il2[--il[j][a%prm[j]]]++;
                    }
                }
                else{ak++;
                    for(ll j:pol){
                        il2[il[j][a%prm[j]]]--;
                        il2[++il[j][a%prm[j]]]++;
                    }
                }
                cz[a]^=1;
                if(!il2[ak])ak--;
                cout<<ak<<"\n";
            }
            for(ll j=0;j<=old.size()+rozw.size();j++)il2[j]=0;
            for(ll k:s){
                for(ll j:pol){
                    --il[j][k%prm[j]];
                }
            }
            rozw.clear();
            dd=-1;
            ds=-1;
        }

        
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    fct[0]=1;
    for(ll i=1;i<FCTCST;i++)fct[i]=fct[i-1]*i;
    ll t=1;
    //cin>>t;
    for(ll i=1;i<=t;i++){
        //cout<<"Case #"<<i<<": ";
        solve();
    }
}