#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
 
//typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> oset;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; }
void _print() { cerr << "]\n"; }

template <typename T, typename... V>
void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }

#ifdef LOCAL
#define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define debug(x...)
#endif

const int mod = 1e9+7;
const ll infi  = 1e18+1;
const ld eps = 1e-14L;

int n, q;

const int MXN = 1e7;
const int MXSMALL = 4000;
const int MXT = 35;

int factor[MXN+3] = {0};
int nxt[MXN+3] = {0};
int largefactor[MXN+3] = {0};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// https://github.com/kth-competitive-programming/kactl/blob/main/content/various/FastInput.h
inline char gc() { // like getchar()
	static char buf[1 << 24];
	static size_t bc, be;
	if (bc >= be) {
		buf[0] = 0, bc = 0;
		be = fread(buf, 1, sizeof(buf), stdin);
	}
	return buf[bc++]; // returns 0 on EOF
}

int readInt() {
	int a, c;
	while ((a = gc()) < 40);
	while ((c = gc()) >= 48) a = a * 10 + c - 480;
	return a - 48;
}

struct Cont {
    //https://github.com/kth-competitive-programming/kactl/blob/main/content/various/FastMod.h
    struct FastMod {
	    ull b, m;
	    FastMod(ull b) : b(b), m(-1ULL / b) {}
	    ull reduce(ull a) { // a % b + (0 or b)
		    return a - (ull)((__uint128_t(m) * a) >> 64) * b;
	    }
    };

    int prime, ans, anscnt;
    vector<int> cnt;
    FastMod fm;
    Cont(int p) : fm(p) {
        prime = p;
        ans = 0;
        anscnt = 0;
        cnt.resize(p);
    }

    void inc(int i) {
        int pos = fm.reduce(i);
        if(pos >= prime) pos -= prime;
        if(cnt[pos]++ == ans){
            anscnt = 1;
            ans++;
        } else if(cnt[pos] == ans){
            anscnt++;
        }
    }

    void dec(int i) {
        int pos = fm.reduce(i);
        if(pos >= prime) pos -= prime;
        if(cnt[pos]-- == ans){
            if(--anscnt == 0){
                ans--;
                for(auto e : cnt){
                    anscnt += (ans == e);
                }
            }
        }
    }
};

struct Small {
    vector<Cont> small;

    Small(vector<int> &primes){
        for(auto &e : primes) small.emplace_back(e);
    }

    int change(int i, bool type) {
        int ans = 0;
        if(type) for(auto &e : small) e.inc(i), ans = max(ans, e.ans);
        else for(auto &e : small) e.dec(i), ans = max(ans, e.ans);
        return ans;
    }
};

struct Large {
    vector<int> alive, ind, uni;
    Large() {
        ind.resize(n+1, -1);
        alive.reserve(q);
    }

    void inc(int i) {
        ind[i] = alive.size();
        alive.push_back(i);
    }

    void dec(int i){
        int id = ind[i];
        int bck = alive.back();
        alive[id] = bck;
        ind[bck] = id;
        alive.pop_back();
        ind[i] = -1;
    }

    int calc() {
        int sajz = alive.size();
        if(sajz <= 1) return sajz;
        int ans = 0;
        uni.reserve(sajz);

        auto solve = [&](int v) -> void {
            uni.clear();
            for(auto e : alive){
                if(e == v) continue;
                int dist = v > e ? v - e : e - v;
                int p = largefactor[dist];
                if(p) uni.push_back(p);
            }
            int res = 1;
            if(!uni.empty()){
                sort(uni.begin(), uni.end());
                int now = 1;
                for(int j=1;j<(int)uni.size();j++){
                    if(uni[j] == uni[j-1]) now++;
                    else {
                        res = max(res, now+1);
                        now = 1;
                    }
                }
                res = max(res, now+1);
            }
            ans = max(ans, res);
        };

        if(sajz < MXT){
            for(auto e : alive) solve(e);
        } else {
            for(int i=0;i<MXT;i++) solve(alive[rng() % sajz]);
        }
        return ans;
    }
};

char obuf[1<<24];
int opos = 0;

void mywrite(int x){
    char tmp[12];
    int len = 0;
    do {
        tmp[len++] = '0' + x % 10;
        x/=10;
    } while(x);
    for(int i=len-1;i>=0;i--) obuf[opos++] = tmp[i];
    obuf[opos++] = '\n'; 
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //cin >> n >> q;
    n = readInt(); q = readInt();
    vector<int> primes, sprimes;
    primes.reserve(n/5);
    for(int i=2;i<=n;i++){
        if(!factor[i]){
            factor[i] = i;
            primes.push_back(i);
            if(i <= MXSMALL) sprimes.push_back(i);
        }
        for(auto e : primes){
            ll j = (ll)e * (ll)i;
            if(j > n || e > factor[i]) break;
            factor[j] = e;
            if(e == factor[i]){
                nxt[j] = nxt[i];
                break;
            } else {
                nxt[j] = i;
            }
        }
    }

    for(int i=2;i<=n;i++){
        int val = i;
        while(val > 1){
            int p = factor[val];
            val = nxt[val];
            if(p > MXSMALL){
                largefactor[i] = p;
                break;
            }
        }
    }

    Small small(sprimes);
    Large large;
    vector<char> alive(n+1, 0);
    int MXLARGE = (2LL * n) / MXSMALL + 5;
    while(q--){
        int i; //cin >> i;
        i = readInt();
        int ans = small.change(i, alive[i] == 0);
        if(alive[i] == 0){
            large.inc(i);
        } else {
            large.dec(i);
        }
        alive[i] ^= 1;
        int sajz = large.alive.size();
        if(sajz < MXLARGE) ans = max(ans, large.calc());
        //cout << ans << '\n';
        mywrite(ans);
    }
    fwrite(obuf, 1, opos, stdout);
    return 0;
}