// Template generated by Clank
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define st first
#define nd second
#define all(x) x.begin(), x.end()
#define BOOST cin.tie(NULL); ios_base::sync_with_stdio(false);
// #define int ll
typedef long long ll;

int n, q;
int np;
int dlim, plim;
int flag1 = (1 << 25);
vector<int> p2i;
vector<int> i2p;
vector<int> sievev;
vector<int> diff_to_mod;

int delctr = 0;
int addctr = 0;

struct AnsTracker{
    vector<int> ir; // ir[i] = ile roznic ktore zgarniaja 'i' kamieni
    vector<vector<int>> strats_s;               // strats_s[i][j] = ile kamieni zgarnia skok co 'i' z przesunieciem 'j' dla i < plim
    vector<gp_hash_table<int, int>> strats_b;   // strats_b[i][j] = ile kamieni zgarnia skok co 'i' z przesunieciem 'j' dla i >= plim
    int curr_max;   // odpowiedz
    AnsTracker(){
        ir.resize(q + 1);
        strats_s.resize(plim);
        for(int i = 0; i < plim; i++){
            strats_s[i].resize(i2p[i], 0);
        }
        strats_b.resize(np - plim + 1);
        curr_max = 0;
    }
    inline int get_ans(){
        return curr_max;
    }

    inline void del_big(int diff, int shift){
        int tmp = --strats_b[diff][shift];
        if(tmp == 1){
            strats_b[diff].erase(shift);
            ir[2]--;
        } else {
            ir[tmp]++;
            ir[tmp + 1]--;
        }
        if(ir[tmp + 1] == 0 && tmp + 1 == curr_max)
            curr_max--;
    }
    inline void del_small(int diff, int shift){
        int tmp = --strats_s[diff][shift];
        ir[tmp]++;
        ir[tmp + 1]--;
        if(ir[tmp + 1] == 0 && tmp + 1 == curr_max)
            curr_max--;
    }

    inline void del(int diff, int shift){
        delctr++;
        diff = p2i[diff];
        if(diff >= plim){
            del_big(diff-plim, shift);
        } else {
            del_small(diff, shift);
        }
    }

    inline void add_small(int diff, int shift){
        // cerr << "ADD small " << diff << " " << shift  << " " << strats_s.size() << endl; 
        int tmp = ++strats_s[diff][shift];
        ir[tmp - 1]--;
        ir[tmp]++;
        curr_max = max(curr_max, tmp);
    }

    inline void add_big(int diff, int shift){
        int tmp = ++strats_b[diff][shift];
        if(tmp == 1){
            ++strats_b[diff][shift];
            ir[2]++;
            curr_max = max(curr_max, 2);
        } else {
            ir[tmp - 1]--;
            ir[tmp]++;
            curr_max = max(curr_max, tmp);
        }
    }

    inline void add(int diff, int shift){
        addctr++;
        diff = p2i[diff];
        if(diff >= plim){
            add_big(diff-plim, shift);
        } else {
            add_small(diff, shift);
        }
    }
};


struct SituationTracker{
    AnsTracker *ans_bender;
    vector<int> a;
    int dctr = 0;
    // set<int> smalld;
    // set<int> bigd;
    set<int> setd[2];
    SituationTracker(AnsTracker *in_ab){
        a.resize(n + 1);
        ans_bender = in_ab;
    }

    void add_diff(int idx){
        int diff;
        for(int i : setd[0]){
            diff = abs(i - idx);
            if(sievev[diff] != 0) diff = sievev[diff];
            if(diff < i2p[plim] || p2i[diff] & flag1) continue;
            // cout << diff << " diff " << endl;
            p2i[diff] |= flag1;
            diff_to_mod.push_back(diff);
            // ans_bender->add(diff, idx % diff);
        }
        for(int idiff : diff_to_mod){
            p2i[idiff] ^= flag1;
            ans_bender->add(idiff, idx % idiff);
        }
        diff_to_mod.clear();
    }

    void del_diff(int idx){
        int diff;
        for(int i : setd[0]){
            diff = abs(i - idx);
            if(sievev[diff] != 0) diff = sievev[diff];
            // cout << diff << " diff " << endl;
            if(diff < i2p[plim] || p2i[diff] & flag1) continue;
            p2i[diff] |= flag1;
            diff_to_mod.push_back(diff);
            // ans_bender->add(diff, idx % diff);
        }
        for(int idiff : diff_to_mod){
            p2i[idiff] ^= flag1;
            ans_bender->del(idiff, idx % idiff);
        }
        diff_to_mod.clear();
    }

    void transfer_to_small(){
        for(int idx : setd[1]){
            // for(int i : setd[0]){
            //     diff = abs(i - idx);
            //     if(sievev[diff] != 0) diff = sievev[diff];
            //     if(diff < i2p[plim]) continue;
            //     ans_bender->add(diff, idx % diff);
            // }
            add_diff(idx);
            setd[0].insert(idx);
        }
        setd[1].clear();
    }

    void add_small(int idx){
        for(int i = 0; i < plim; i++){
            ans_bender->add(i2p[i], idx % i2p[i]);
        }
        // for(int i : setd[0]){
        //     diff = abs(i - idx);
        //     if(sievev[diff] != 0) diff = sievev[diff];
        //     if(diff < i2p[plim]) continue;
        //     ans_bender->add(diff, idx % diff);
        // }
        add_diff(idx);
        setd[0].insert(idx);
    }

    void add_big(int idx){
        for(int i = 0; i < plim; i++){
            ans_bender->add(i2p[i], idx % i2p[i]);
        }
        setd[1].insert(idx);
    }

    void del_small(int idx){
        for(int i = 0; i < plim; i++){
            ans_bender->del(i2p[i], idx % i2p[i]);
        }
        // for(int i : setd[0]){
        //     diff = abs(i - idx);
        //     if(sievev[diff] != 0) diff = sievev[diff];
        //     if(diff < i2p[plim]) continue;
        //     ans_bender->del(diff, idx % diff);
        // }
        del_diff(idx);
        setd[0].erase(idx);
        if(dctr - 1 <= dlim)
            transfer_to_small();
    }

    void del_big(int idx){
        for(int i = 0; i < plim; i++){
            ans_bender->del(i2p[i], idx % i2p[i]);
        }
        setd[1].erase(idx);
        if(dctr - 1 <= dlim)
            transfer_to_small();
    }

    int add(int idx){
        if(dctr < dlim){
            add_small(idx);
            dctr++;
            return 1;
        } else {
            add_big(idx);
            dctr++;
            return 2;
        }
    }

    void del(int idx){
        if(a[idx] == 1){
            del_small(idx);
        } else {
            del_big(idx);
        }
        dctr--;
    }

    int modify(int ai){
        if(a[ai] == 0){
            a[ai] = add(ai);
        } else {
            del(ai);
            a[ai] = 0;
        }
        return max(min(dctr, 2),ans_bender->get_ans());
    }
};

void sieve(int lim){
    sievev.assign(lim + 1, 0);
    p2i.resize(lim + 1);
    sievev[0] = 1;
    sievev[1] = 1;
    for(int i = 2; i <= lim; i++){
        if(!sievev[i]){
            p2i[i] = (int)i2p.size();
            i2p.push_back(i);
            for(int j = i + i; j <= lim; j += i){
                sievev[j] = i;
            }
        }
    }

    np = (int)i2p.size();
}
 
int32_t main(){
    BOOST;
    cin >> n >> q;
    sieve(1e7 + 1);
    // 501 4196
    // 2160 1150
    int mini = 1e9;
    int miniidx = 10;
    int miniplim = 10;
    for(int i = 10; i <= 5000; i++){
        int idx2 = 0;
        while(i2p[idx2] <= n / i){
            idx2++;
        }
        if(mini >=  idx2 + i){
            mini =  idx2 + i;
            miniidx = i;
            miniplim = idx2;
            // cout << "    ";
        }
        // cout << i << " " << idx2 << " " << idx2 + i << " " << pier[idx2] << " " << idx2 + idx2 + i << "\n";
    }
    // cout << miniidx << " " << mini << "\n";

    dlim = max(10, miniidx) + 10;
    plim = max(10, miniplim) + 10;
    // dlim = 1450;
    // plim = 1700;
    AnsTracker ans_bender;
    SituationTracker situation_bender(&ans_bender);
    int ai;
    while(q--){
        cin >> ai;
        // situation_bender.modify(ai);
        cout << situation_bender.modify(ai) << "\n";
    }
    // cout << addctr << " - " << delctr << "\n";
    return 0;
}