#include <bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
#define VI vector<int>
#define VPII vector<PII>
#define LL long long
#define LD long double
#define f first
#define s second
#define MP make_pair
#define PB push_back
#define endl '\n'
#define ALL(c) (c).begin(), (c).end()
#define SIZ(c) (int)(c).size()
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, b, e) for(int i = (b); i <= (int)(e); ++i)
#define FORD(i, b, e) for(int i = (b); i >= (int)(e); --i)
#define ll LL
#define st f
#define nd s
#define pb PB
#define mp MP
#define eb emplace_back
#define siz(c) SIZ(c)
const int inf = 1e9+7;
const ll INF = 1e18L+7;

#define sim template<class n
sim, class s> ostream & operator << (ostream &p, pair<n, s> x)
{return p << "<" << x.f << ", " << x.s << ">";}
sim> auto operator << (ostream &p, n y) ->
typename enable_if<!is_same<n, string>::value, decltype(y.begin(), p)>::type 
{int o = 0; p << "{"; for(auto c: y) {if(o++) p << ", "; p << c;} return p << "}";}
void dor() {cerr << endl;}
sim, class...s> void dor(n p, s...y) {cerr << p << " "; dor(y...);}
sim, class s> void mini(n &p, s y) {if(p>y) p = y;}
sim, class s> void maxi(n &p, s y) {if(p<y) p = y;}
#ifdef DEB
#define debug(...) dor(__FUNCTION__, ":", __LINE__, ": ", __VA_ARGS__)
#else
#define debug(...)
#endif 

#define I(x) #x " =", (x), " "
#define A(a, i) #a "[" #i " =", i, "] =", a[i], " "


struct FastRand {
    uint64_t x;
    FastRand(uint64_t seed = 88172645463325252ULL) : x(seed) {}
    
    uint64_t next() {
        x ^= x << 13;
        x ^= x >> 7;
        x ^= x << 17;
        return x;
    }

    uint64_t nextInt(uint64_t n) { // [0, n-1]
        return (__uint128_t)next() * n >> 64;
    }
} rng;

const int MAXN = 1e7+7;
const int MAXQ = 1e6+7;
const int MAXP = 1000; // wszystko mniejsze brutem

const int START_FULL_SOLUTION = 2 * MAXN / MAXP + 1; // 20k - jak spadnie ponizej to chcemy miec wynik
const int STOP_FULL_SOLUTION = 3 * MAXN / MAXP + 1; // 30k - jak przekroczymy przestajemy trzymac wynik



int divs[MAXN]; // 0 jeśli pierwsza, jeśli nie to najwiekszy dzielnik
// int divs_bigger[MAXN];
void preprocess() {
    divs[1] = 1;
    for(int i = 2; i < MAXN; ++i) {
        if(divs[i] == 0) { // prime or 1
            for(int j = i; j < MAXN; j += i) {
                divs[j] = i;
            }
        }
    }
}

vector<int> primes1000;
vector<int> offsets;
int count_small_flat[MAXN];
bitset<MAXN> inserted;
int input[MAXQ];
int answer[MAXQ];
int num_with_freq[MAXQ];


// **********************
const int KEEP_ANSWERS = 4;
const float CHANGE_ANSWERS = 1.5;

vector<pair<PII, int>> answers; // (i, prime), count | accepted if (value - i) % prime == 0
vector<int> alive;
vector<vector<PII>> alive_voting;
int pos_alive[MAXN]; // gdzie jest ktory wrzucony 

const int SUBSET_SIZE = 50;
const int THRESHOLD = 5; // jaka frakcja wymagana

int subset[SUBSET_SIZE * 100];
int generate_random_subset() { // uwaga! z powtrzeniami
    if(alive.size() < SUBSET_SIZE) {
        REP(i, alive.size()) {
            subset[i] = alive[i];
        }
        return alive.size();
    }

    for(int i = 0; i < SUBSET_SIZE; ++i) {
        subset[i] = alive[rng.nextInt(alive.size())];
    }
    return SUBSET_SIZE;
}

int got_primes[SUBSET_SIZE * 100][2]; // each guy at most two primes > 1000

int primes_count[MAXN];
int p1 = 0, p2 = 0, p3 = 0;


int BEST_BRUTE = 0;
inline void add_prime(int d, int at_least) {
    primes_count[d]++;
    BEST_BRUTE = max(BEST_BRUTE, primes_count[d]);

    if(primes_count[d] >= at_least) {
        if(p1 == 0)p1 = d;
        if(p1 != d && p2 == 0)  p2 = d;
        if(p1 != d && p2 != d && p3 == 0) p3 = d;
    }
}

VPII compute_one_with_value(int val, int count) {
    int at_least = count / THRESHOLD + 1;
    p1 = p2 = p3 = 0;

    REP(i, count) {
        got_primes[i][0] = got_primes[i][1] = 0;
        if(val == subset[i])continue;

        subset[i] = abs(subset[i] - val);
        int d = divs[subset[i]];

        if(d > MAXP) {
            got_primes[i][0] = d; // first prime > MAXP
            add_prime(d, at_least);

            subset[i] /= d;
            d = divs[subset[i]]; 
            if(d > MAXP && d != got_primes[i][0]) { // skip the square!!
                got_primes[i][1] = d;
                add_prime(d, at_least);
            }
        }
    }
    REP(i, count) {
        primes_count[got_primes[i][0]] = 0;
        primes_count[got_primes[i][1]] = 0;
    }

    VPII res;
    if(p1)res.push_back({val % p1, p1});
    if(p2)res.push_back({val % p2, p2});
    if(p3)res.push_back({val % p3, p3});
    return res;
}

int go_brute() {
    if(alive.size() == 0)return 0;
    BEST_BRUTE = 0;

    for(int i = 0; i * 2 < alive.size(); i++) {
        int p = 0;
        REP(j, alive.size()) {
            if(i != j)
                subset[p++] = alive[j];
        }
        compute_one_with_value(alive[i], alive.size()-1);
    }
    return BEST_BRUTE + 1;
}

inline void update(pair<PII, int> &ans, int val, int change) {
    if((val - ans.f.f) % ans.f.s == 0) {
        ans.s += change;
    }
}

map<PII, int> votes;
set<pair<int, PII> > ranking_votes;

void add_votes(PII vote, int change) {
    if(votes.count(vote)) {
        ranking_votes.erase({votes[vote], vote});
    }
    votes[vote] += change;

    if(votes[vote] > 0) {
        ranking_votes.insert({votes[vote], vote});
    }
}

PII best_ranking_votes() { // not in answer
    auto it = ranking_votes.rbegin();
    while(it != ranking_votes.rend()) {
        bool ok = 1;
        for(auto i: answers)
            if(i.f == it->s) {
                ok = 0;
                break;
            }
        if(ok)return it->s;
        it++;
    }
    return MP(0, 0);
}


void add_votes(VPII &vote, int change) {
    for(auto i: vote)
        add_votes(i, change);
}

int RECOMPUTE_WORK = 0;
int recompute(PII cand) {
    RECOMPUTE_WORK += alive.size();
    int res = 0;
    for(auto i: alive) {
        if((i - cand.f) % cand.s == 0)res++;
    }
    return res;
}

int q;
void real_solve() {
    inserted.reset();
    REP(i, q) {
        debug(i);

        int in = input[i];
        if(!inserted[in]) { // add
            for(auto &i: answers) {
                update(i, in, 1);
            }
            int got = generate_random_subset(); // without newest one

            alive.push_back(in);
            pos_alive[in] = alive.size() - 1;

            auto cands = compute_one_with_value(in, got);
            alive_voting.push_back(cands);
            add_votes(cands, 1);
        }
        else { // remove
            for(auto &i: answers) {
                update(i, in, -1);
            }
            int alive_idx = pos_alive[in];
            swap(alive[alive_idx], alive.back());
            swap(alive_voting[alive_idx], alive_voting.back());

            pos_alive[alive[alive_idx]] = alive_idx;
            alive.pop_back();
            add_votes(alive_voting.back(), -1);
            alive_voting.pop_back();

            // TODO: many reps?

            if(alive.size())
            REP(_, 3) {
                int got = generate_random_subset();
                int redo = rng.nextInt(alive.size());
                auto cands = compute_one_with_value(alive[redo], got);

                add_votes(alive_voting[redo], -1);
                add_votes(cands, 1);
                alive_voting[redo] = cands;
            }
        }

        inserted.flip(in);
        sort(ALL(answers), [](auto &a, auto &b) {
            return votes[a.f] > votes[b.f];
        });


        while(answers.size() < KEEP_ANSWERS && answers.size() < votes.size() && alive.size() < 40 * 1000) {
            auto new_cand = best_ranking_votes();
            if(new_cand.s == 0)break;
            answers.push_back({new_cand, recompute(new_cand)});
        }

        auto new_cand = best_ranking_votes();
        if(answers.size() && new_cand.s && votes[answers.back().f] * CHANGE_ANSWERS < votes[new_cand] - 10 && alive.size() < 40 * 1000) {
            answers.pop_back();
            answers.push_back({new_cand, recompute(new_cand)});
        }



        for(auto i: answers) {
            debug(i, votes[i.f]);
        }



        int best = 0;
        for(auto i: answers)
            maxi(best, i.s);

        if(alive.size() < 20) {
            maxi(answer[i], go_brute());
        }
        maxi(answer[i], best);

        debug(i, alive.size());
    }
}


int32_t main() {
    preprocess(); // 0.4s

    int s = 0;
    FOR(i, 2, MAXP) {
        if (divs[i] == i) {
            primes1000.push_back(i);
            offsets.push_back(s);
            s += i;
        }
    }
    debug(I(s));
    debug(I(primes1000), primes1000.size());

    int n;
    ios_base::sync_with_stdio(0);


    cin >> n >> q;
    // n = 1e7;q = 1e6;
    REP(i, q) {
        cin >> input[i];
        // input[i] = rand() % n + 1;
    }
    debug(n, q);
    int best = 0;

    REP(i, q) {
        int in = input[i];
        if(!inserted[in]) {
            REP(_j, primes1000.size()) {
                int j = primes1000[_j];
                int rem = in % j;
                
                int &val = count_small_flat[offsets[_j] + rem];
                num_with_freq[val]--;
                val++;
                num_with_freq[val]++;
                
                maxi(best, val);
            }
        }
        else {
            REP(_j, primes1000.size()) {
                int j = primes1000[_j];
                int rem = in % j;
                
                int &val = count_small_flat[offsets[_j] + rem];
                num_with_freq[val]--;
                
                if (val == best && num_with_freq[val] == 0) {
                    best--;
                }
                
                val--;
                num_with_freq[val]++;
            }
        }
        inserted.flip(in);
        answer[i] = best;
    }

    real_solve(); 

    REP(i, q) {
        cout << answer[i] << endl;
    }

    debug(RECOMPUTE_WORK);
}