#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef double db;
typedef pair<int, int> pii;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define rep(i, l, r) for(int i=l; i<(r); i++)

mt19937 rng(random_device{}());
int rd(int l, int r) {
    //return l + (rand()%(1+r-l));
	return uniform_int_distribution<int>(l, r)(rng);
}

const int N = 1e7;
const int Q = 1e6;
bool nonprime[N+1];
const int IlePierwszych = 664'579;
int pierwsze[IlePierwszych];
int duzyDzielnik[N+1];
const int Limit_na_male = 3163; // 5000
const int IleMalych = 447; //669;
int wyniki_dla_malych[IleMalych][Limit_na_male];

int d = 0;
bool tab[N+1];

int ans_maly = 0;
int ile_takich[Q+1];

void sito() {
    for(int i=1; i<=N; i++) duzyDzielnik[i] = i;
    int ile_juz = 0;
    nonprime[0] = 1;
    nonprime[1] = 1;
    for(int i=2; i <= Limit_na_male; i++) {
        if(nonprime[i]) continue;
        duzyDzielnik[i] = 1;
        for(int j = 2*i; j <=N; j+=i) {
            while(duzyDzielnik[j]%i == 0) duzyDzielnik[j]/=i;
            nonprime[j] = 1;
        }
    }
    for(int i=2; i<=N; i++) {
        if(!nonprime[i]) pierwsze[ile_juz++] = i;
    }
}


bool jest_u_nas[N+1];
vector<int> wszystkie;

void dodaj_do_wszystkich(int val) {
    if(!jest_u_nas[val]) wszystkie.push_back(val);
    jest_u_nas[val]=1;
}

int daj_losowy() {
    while(!wszystkie.empty()) {
        int siz = wszystkie.size();
        int pozycja = rd(0, siz-1);
        int ktory = wszystkie[pozycja];
        if(tab[ktory]) return ktory;
        else {
            swap(wszystkie[pozycja], wszystkie[siz-1]);
            wszystkie.pop_back();
            jest_u_nas[ktory] = 0;
        }
    }
    return -1;
}

void oczysc_wszystkie() {
    for(int i=0; i<wszystkie.size(); i++) {
        if(!tab[wszystkie[i]]) {
            jest_u_nas[wszystkie[i]] = 0;
            swap(wszystkie[i], wszystkie.back());
            wszystkie.pop_back();
            i--;
        }
    }
}

int brutuj() {
    oczysc_wszystkie();
    assert(wszystkie.size() == d);
    int ans = min(d, 2);
    for(int i=0; i<d; i++) {
        for(int j=i+1; j<d; j++) {
            int roz = abs(wszystkie[i]-wszystkie[j]);
            int p = duzyDzielnik[roz];
            if(p > 1) {
                int r = wszystkie[i]%p;
                int proba = 2;
                for(int k=j+1; k<d; k++) {
                    if(wszystkie[k]%p == r) proba++;
                }
                ans = max(ans, proba);
            }
        }
    }
    return ans;
}
map<pii, int> duze;
// vector<pair<<pii, int>> duze;
// vector<pair<<pii, int>>> do_dodania;
const int Lbrut = 10; // ile najwiecej zeby brucic
const int IleLosowanNaRuch = 20;
const int IleSprawdzanNaRuch = 2;
int ileLosowan = 0;
const int ilePonizej = 10;


void recount_small(int a, bool dodajemy) {
    if(dodajemy) {
        tab[a] = true;
        dodaj_do_wszystkich(a);
        d++;
        for(int i=0; i<IleMalych; i++) {
            int p = pierwsze[i];
            int moje = a%p;
            wyniki_dla_malych[i][moje]++;
            int proba = wyniki_dla_malych[i][moje];
            ile_takich[proba]++;
            ile_takich[proba-1]--;
            if(proba > ans_maly) ans_maly = proba;
        }
    }
    else {
        tab[a] = false;
        d--;
        for(int i=0; i<IleMalych; i++) {
            int p = pierwsze[i];
            int moje = a%p;
            wyniki_dla_malych[i][moje]--;
            int proba = wyniki_dla_malych[i][moje];
            ile_takich[proba]++;
            ile_takich[proba+1]--;
            if(ile_takich[ans_maly]==0) ans_maly--;
        }
    }
}

int duzy_wynik = 0;
void obsluz_duze(int a, bool dodajemy) {
    for(auto it = duze.begin(); it!=duze.end(); ) {
        int ile = it->second;
        if(a%it->first.first == it->first.second) {
            if(dodajemy) ile++;
            else ile--;
        }
        if(ile < max(ans_maly - ilePonizej, 3)) {
            it = duze.erase(it);
        }
        else{
            it->second = ile;
            it++;
        }
        duzy_wynik = max(duzy_wynik, ile);
    }
}

void solve(){
    int n, q;
    cin >> n >> q;
    while(q--) {
        int a;
        cin >> a;
        bool dodajemy = !tab[a];
        recount_small(a, dodajemy);
        duzy_wynik = max(0, duzy_wynik-1);
        obsluz_duze(a, dodajemy);


        ileLosowan += IleLosowanNaRuch;
        if(d <= Lbrut) duzy_wynik = max(duzy_wynik, brutuj());
        else {
            vector<pii> todo;
            while(ileLosowan--) {
                int uno = daj_losowy();
                int dos = uno;
                while(dos == uno) dos = daj_losowy();
                int roz = abs(dos-uno);
                if(duzyDzielnik[roz] > 1) {
                    int p = duzyDzielnik[roz];
                    int res = uno%p;
                    if(duze.count({p, res})) continue;
                    todo.emplace_back(p, res);
                }
            }
            sort(all(todo));
            vector<pair<int, pii>> counted_todo;
            int ile_pod_rzad = 1;
            for(int i=1; i<=sz(todo); i++) {
                if(i < sz(todo) && todo[i] == todo[i-1]) ile_pod_rzad++;
                else {
                    counted_todo.push_back({ile_pod_rzad, todo[i-1]});
                    ile_pod_rzad = 1;
                }
            }
            sort(all(counted_todo));
            reverse(all(counted_todo));
            for(int i=0; i<min(sz(counted_todo), IleSprawdzanNaRuch); i++) {
                int p = counted_todo[i].second.first;
                int res = counted_todo[i].second.second;
                int proba_tutaj = 0;
                if(n/p < 2*d){
                    for(int i=res; i<=n; i+=p) { // jesli jest malo liczb to mozna zamiast tego przejsc po wszystkich
                        if(tab[i]) proba_tutaj++;
                    }
                }
                else {
                    oczysc_wszystkie();
                    for(auto e : wszystkie) {
                        if(e%p == res) proba_tutaj++;
                    }
                }
                if(proba_tutaj >= max(ans_maly - ilePonizej, 3)) { // TODO : zastanowic sie nad tym boundem
                    duze[{p, res}] = proba_tutaj;
                }
                // do_dodania.push_back({(pii){p, res}, proba_tutaj});
                duzy_wynik = max(duzy_wynik, proba_tutaj);
            }
        }
        cout << max(ans_maly, duzy_wynik) << "\n";
    }
}

int main(){
    sito();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}