//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<class T>
using vec = vector<T>;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KoRoVa
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = 1e7 + 11, inf = 1000111222;


mt19937 rng(228);
template<typename T = int>
inline T randll(T l = INT_MIN, T r = INT_MAX) {
    return uniform_int_distribution<T>(l, r)(rng);
}

inline ld randld(ld l = INT_MIN, ld r = INT_MAX) {
    return uniform_real_distribution<ld>(l, r)(rng);
}



int have[max_n];

int mn[max_n];

const int C = 90;

const int BIG = 1000;

int id[max_n];

vector <int> pr;


int t_mem[max_n];


struct segment {
    int *t;
    int n;

    segment (int n, int *_t) : t(_t), n(n) {}


    inline void upd (int v, int val) {
        v += n;
        t[v] += val;
        for (; v > 1 ; v >>= 1) {
            t[v >> 1] = max(t[v], t[v ^ 1]);
        }
    }

    inline int get_val () {
        return t[1];
    }
};

bool cnt[max_n];

int gg[max_n];


pii l[2000];

map <pii, ll> save;


const int max_q = 1e6 + 11;

pii q_mx[max_q];
pii q_second_mx[max_q];

int val[max_n];

int cur_num = 0;

int gen(int m) {
//    return randll(0, m - 1);
    if (m == 1) {
        return 0;
    }
    ++cur_num;
    if (cur_num >= max_q) {
        cur_num -= max_q;
    }
    if (val[cur_num] < m) {
        return val[cur_num];
    }
    return val[cur_num] % m;
}

int main() {
//    freopen("103.in", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);


    int pos_mem = 0;
    vector <segment> t;
    for (int i = 2, num = 0; i < max_n; i++) {
        if (mn[i] == 0) {
            id[i] = num++;
            if (i < BIG) {
                pr.pb(i);

                t.pb(segment(i, t_mem + pos_mem));

                pos_mem += i + i;
            }
            for (int j = i; j < max_n; j += i) {
                if (!mn[j]) {
                    mn[j] = i;
                }
            }
        }
    }



    for (int i = 0; i < max_q; i++) {
        val[i] = randll(0, max_q);
    }


    for (int i = BIG; i < max_n; i++) {
        if (mn[i] == i) {
            for (int j = i; j < max_n; j += i) {
                if (!gg[j]) {
                    gg[j] = i;
                }
            }
        }
    }


//    LOG(pos_mem, len(t));
    assert(pos_mem < max_n);

    for (int i = 1; i < max_n; i++) {
        have[i] = -1;
    }

    int n, q;
    cin >> n >> q;
    vector <int> now;

    int res = 0;

    auto upd = [&] (int x, int val) {
        res = 0;
        for (int i = 0; i < len(pr); i++) {
            int y = x % pr[i];
            t[i].upd(y, val);
            umax(res, t[i].get_val());
        }
    };

    auto calc = [&] (int b, int ost) {
        if (b == 0) {
            return 0;
        }
        int cur = 0;
        for (int x: now) {
            if ((x % b) == ost) {
                ++cur;
            }
        }
        return cur;
    };

    int prv = 0;

    auto solve = [&] (int id) {
        int k = len(now);
        if (k == 0) {
            return 0;
        }
        int ans = max({1, res, prv - 1});

//        vector <pii> have;
        int num = 0;
        for (int it = 0; it < C; it++) {
            int x = gen(len(now));
            int y = gen(len(now));
            int val = abs(now[x] - now[y]);
            if (val == 0) {
                continue;
            }
            int X = now[x];
            while (val > 1) {
                int d = gg[val];
                if (d == 0) {
                    break;
                }
                if (n > ans * 1LL * d) {
//                    LOG("ok");
                    l[num++] = {d, X % d};
//                    continue;
//                    umax(ans, calc(d, X % d));
                }
                else {
                    break;
                }

                while (val % d == 0) {
                    val /= d;
                }
            }
        }
//        return 0;
        if (num) {
            sort(l, l + num);
            pair<int, pii> mx(0, {0, 0}), mx2(0, {0, 0});
            for (int i = 0; i < num;) {
                int j = i;
                while (j < num && l[j] == l[i]) {
                    ++j;
                }
                int c = j - i;
                if (mx.first < c) {
//                    umax(ans, calc(mx2.second.first, mx2.second.second));
                    mx2 = mx;
                    mx = {c, l[i]};
                } else if (mx2.first < c) {
//                    umax(ans, calc(mx2.second.first, mx2.second.second));
                    mx2 = {c, l[i]};
                }
                else {
//                    umax(ans, calc(l[i].first, l[i].second));
                }
                i = j;
            }
//            LOG(num, mx.first, mx2.first);

            if (mx.first > 0) {
                int b = mx.second.first;
                int ost = mx.second.second;
                if (len(now) < 100) {
                    int cur = calc(b, ost);

                    umax(ans, cur);
                }
                else {

                    save[{b, ost}] += min(len(now), n / b);

                    q_mx[id] = mx.second;
                }
            }
            if (mx2.first > 0) {
                int b = mx2.second.first;
                int ost = mx2.second.second;
                if (len(now) < 100) {
                    int cur = calc(b, ost);

                    umax(ans, cur);
                }
                else {

                    save[{b, ost}] += min(len(now), n / b);

                    q_second_mx[id] = mx2.second;
                }
            }
        }


        return ans;
    };
    vector <int> ans(q), a(q);
    for (int it = 0; it < q; it++) {
        int x;
        cin >> x;
        a[it] = x;
        if (have[x] == -1) {
            have[x] = len(now);
            now.pb(x);
            upd(x, 1);
        }
        else {
            int pos = have[x];
            if (pos + 1 != len(now)) {
                int who = now.back();
                swap(now[pos], now.back());
                swap(have[who], have[x]);
            }
            have[x] = -1;
            now.pop_back();
            upd(x, -1);
        }
        cnt[x] ^= 1;
        ans[it] = solve(it);
        prv = ans[it];
    }


//    LOG("here", clock() / CLOCKS_PER_SEC);



    vector <pair<ll, pii> > wow;
    wow.reserve(2 * q);
    for (auto &i : save) {
        wow.push_back({i.second, i.first});
    }

    sort(all(wow));
    reverse(all(wow));
//    LOG(len(wow));
    if (len(wow) > 20) {
        wow.resize(20);
    }
    reverse(all(wow));
    vector <pii> cur_wow;
    for (auto &i : wow) {
        cur_wow.pb(i.second);
    }
    sort(all(cur_wow));




    vector <int> results(len(wow));


    auto check = [&] (int id, pii mx) {
        if (mx.first == 0) {
            return;
        }
        int b = mx.first;
        int ost = mx.second;
//        umax(ans[id], calc(b, ost));
//        return;
        int j = lower_bound(all(cur_wow), mx) - cur_wow.begin();
        if (j != len(cur_wow) && cur_wow[j] == mx) {
            umax(ans[id], results[j]);
            return;
        }
        if (len(now) < n / b) {
            umax(ans[id], calc(b, ost));
        }
        else {
            int cur = 0;
            for (int i = ost; i <= n; i += b) {
                cur += cnt[i];
            }
            umax(ans[id], cur);
        }
    };

    for (int i = 0; i < max_n; i++) {
        cnt[i] = 0;
        have[i] = -1;
    }
    now.clear();
    for (int it = 0; it < q; it++) {
        int x = a[it];
        if (cnt[x] == 0) {
            have[x] = len(now);
            now.pb(x);
            for (int j = 0; j < len(cur_wow); j++) {
                if ((x % cur_wow[j].first) == cur_wow[j].second) {
                    ++results[j];
                }
            }
        }
        else {
            for (int j = 0; j < len(cur_wow); j++) {
                if ((x % cur_wow[j].first) == cur_wow[j].second) {
                    --results[j];
                }
            }

            int pos = have[x];
            if (pos + 1 != len(now)) {
                int who = now.back();
                swap(now[pos], now.back());
                swap(have[who], have[x]);
            }
            have[x] = -1;
            now.pop_back();
        }
        cnt[x] ^= 1;



        check(it, q_mx[it]);
        check(it, q_second_mx[it]);
    }


    for (auto &i : ans) {
        cout << i << '\n';
    }
}

/*
KoRoVa!
*/