#include <bits/stdc++.h>
using namespace std;
#define fwd(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) fwd(i, 0, n)
#define all(X) X.begin(), X.end()
#define sz(X) int(size(X))
#define pb push_back
#define eb emplace_back
#define st first
#define nd second
using pii = pair<int, int>; using vi = vector<int>;
using ll = long long; using ld = long double;
#ifdef LOC
auto SS = signal(6, [](int) { *(int *)0 = 0; });
#define DTP(x, y) auto operator<<(auto &o, auto a) -> decltype(y, o) { o << "("; x; return o << ")"; }
auto operator<<(auto &o, auto a) -> decltype(all(a), o);
DTP(o << a.st << ", " << a.nd, a.nd);
DTP(for (auto i : a) o << i << ", ", all(a));
#define deb(x...) cerr << setw(4) << __LINE__ << ":[" #x "]: ", [](auto... arg_) { (( cerr << arg_ << ", " ), ...) << '\n'; }(x)
#else
#define deb(...) 0
#endif

bool shouldQuit() {
    return (double)clock() >= 8.5 * CLOCKS_PER_SEC;
}

// SMALL_PRIMES_CNT == 450 for [smallPrimes.back()] > sqrt(M)
const int M = 1.1e7, MAXQ = 1.1e6;
const int SMALL_PRIMES_CNT = 150;
// const int SMALL_PRIMES_CNT = 450; jedna lp na iteracje
const int MIN_PORTION = 5;
const int WPISY_CNT = 12;

mt19937_64 rnd;
struct FastSet {
    vi pos, nums;

    FastSet() : pos(M, -1) {}

    void insert(int i) {
        assert(pos[i] == -1);
        pos[i] = size();
        nums.pb(i);
    }

    void erase(int i) {
        assert(pos[i] != -1);
        if (i != nums.back()) {
            int j = nums.back();
            nums[pos[j] = pos[i]] = j;
        }
        pos[i] = -1;
        nums.pop_back();
    }

    bool contains(int i) { return pos[i] != -1; }
    int size() { return (int)nums.size(); }
    bool empty() { return nums.empty(); }
    int pick() {
        assert(!empty());
        return nums[rnd() % size()];
    }

    void clear() {
        for (int i : nums) pos[i] = -1;
        nums.clear();
    }
} fastset;

vi primes, sieve;
vi smallPrimes;
vector<array<int, 2>> largeDivs;

void pushToArray(array<int, 2> &ref, int i) {
    if (ref[0]) {
        assert(!ref[1]);
        ref[1] = i;
    }
    else ref[0] = i;
}

bool pushToArray(array<pii, WPISY_CNT> &ref, pii p) {
    if (ref.back().st)
        return false;;
    rep(i, sz(ref)) {
        // assert(ref[i] != p); todo co z tym zrobic
        if (ref[i].st == 0) {
            ref[i] = p;
            return true;
        }
    }
    assert(false);
}

void initSieve() {
    sieve.resize(M);
    largeDivs.resize(M);
    fwd(p, 2, sz(sieve)) {
        if (sieve[p]) continue;
        primes.pb(p);
        bool isSmall = sz(smallPrimes) < SMALL_PRIMES_CNT;
        if (isSmall)
            smallPrimes.pb(p);

        for (int i = p; i < M; i += p) {
            sieve[i] = p;
            if (!isSmall) pushToArray(largeDivs[i], p);
        }
    }
}

// true == add
vi solveSmallPrimes(const vector<pair<bool, int>> &q) {
    initSieve();

    vi cnts, offsets;
    vi cntOfCounts(MAXQ); cntOfCounts[0] = 1e9;

    rep(i, sz(smallPrimes)) {
        int p = smallPrimes[i];
        offsets.pb(sz(cnts));
        cnts.resize(sz(cnts) + p);
    }

    deb(sz(cnts));

    int A = 0;
    vi res;
    int cnttotal = 0;

    for (auto [add, x] : q) {
        if (add) {
            ++cnttotal;
            rep(i, sz(smallPrimes)) {
                int p = smallPrimes[i];
                int &ref = cnts[offsets[i] + x % p];
                --cntOfCounts[ref];
                ++ref;
                ++cntOfCounts[ref];
            }
            if (cntOfCounts[A+1]) ++A;
        }
        else {
            --cnttotal;
            rep(i, sz(smallPrimes)) {
                int p = smallPrimes[i];
                int &ref = cnts[offsets[i] + x % p];
                --cntOfCounts[ref];
                --ref;
                ++cntOfCounts[ref];
            }
            if (!cntOfCounts[A]) --A;
        }
        res.pb(max(A, min(2, cnttotal)));
    }

    return res;
}

void heuraOnce(vi &ans, const vector<pair<bool, int>> &queries, vector<array<pii, WPISY_CNT>> &wpisy, int iterid) {
    uniform_real_distribution urd;
    fastset.clear();

    int fullruns = 0;
    int anyChange = false;

    rep(qidst, sz(queries)) {
        {
            auto [add, x] = queries[qidst];
            if (add)
                fastset.insert(x);
            else
                fastset.erase(x);
        }

        if (fastset.size() <= 2 || urd(rnd) > 3.0 / fastset.size())
            continue;

        int A = fastset.pick(), B = fastset.pick(), C = fastset.pick(), D = fastset.pick();
        int gc = gcd(A-B, gcd(B-C, C-D));

        for (int p : largeDivs[gc]) if (p) {
            int r = A % p;
            // deb(pii(p, r), qidst);
            int cntGoodQidst = 0;
            for (int n : fastset.nums) if (n % p == r) ++cntGoodQidst;
            ++fullruns;

            bool hasValue = false;
            rep(i, sz(wpisy[qidst])) {
                if (wpisy[qidst][i].st == 0) break;
                if (wpisy[qidst][i] == pair(p, r)) {
                    hasValue = true;
                    break;
                }
            }
            if (hasValue) continue;

            int cntGood = cntGoodQidst;
            int cntTotal = fastset.size();

            auto breakCondition = [](int cntGood, int cntTotal) {
                return cntGood * MIN_PORTION < cntTotal || cntTotal <= 2 || cntGood < 2;
            };
            if (breakCondition(cntGood, cntTotal)) continue;

            for (int i = qidst; i >= 0; --i) {
                if (breakCondition(cntGood, cntTotal)) break;
                // deb("pushed to", i, pii(p, r));
                pushToArray(wpisy[i], {p, r});

                if (cntGood > ans[i]) {
                    // deb(i, cntGood, ans[i], iterid);
                    anyChange++;
                    ans[i] = cntGood;
                }

                auto [add, x] = queries[i];
                if (x % p == r) cntGood += add ? -1 : 1;
                cntTotal += add ? -1 : 1;
            }

            cntGood = cntGoodQidst;
            cntTotal = fastset.size();

            for (int i = qidst+1; i < sz(queries); ++i) {
                auto [add, x] = queries[i];
                if (x % p == r) cntGood += add ? 1 : -1;
                cntTotal += add ? 1 : -1;

                if (breakCondition(cntGood, cntTotal)) break;
                pushToArray(wpisy[i], {p, r});

                if (cntGood > ans[i]) {
                    // deb(i, cntGood, ans[i], iterid);
                    anyChange++;
                    ans[i] = cntGood;
                }
            }
        }

        if (shouldQuit())
            return;
    }

    if (anyChange)
        deb(iterid, fullruns, anyChange, clock()*1.0/CLOCKS_PER_SEC);
}

int solveOnceBrute(vi v) {
    int ans = (sz(v) + 1) / 2;

    auto check = [&](int p, int r) {
        int c = 0;
        for (int i : v) if (i % p == r)
            ++c;
        ans = max(ans, c);
    };

    for (int i : v) for (int j : v) if (i > j) {
        int d = i - j;
        while (d > 1) {
            int p = sieve[d];
            while (d % p == 0)
                d /= p;
            check(p, i % p);
        }
    }

    return ans;
}

vi solve(const vector<pair<bool, int>> &q) {
    auto ans = solveSmallPrimes(q);

    vector<array<pii, WPISY_CNT>> wpisy(sz(q));

    int id = 0;
    while (!shouldQuit())
        heuraOnce(ans, q, wpisy, id++);
    deb("CALLS COMPL", id);

    return ans;
}

vi solve(const vi &q) {
    vector<pair<bool, int>> an(sz(q));
    rep(i, sz(q)) {
        an[i] = {!fastset.contains(q[i]), q[i]};
        if (an[i].first) fastset.insert(q[i]);
        else fastset.erase(q[i]);
    }
    fastset.clear();
    return solve(an);
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int _, qq;
    cin >> _ >> qq;
    vi q(qq);
    rep(i, sz(q)) {
        cin >> q[i];
    }

    q = solve(q);
    for (int i : q)
        cout << i << '\n';
}