#include <bits/stdc++.h>

using namespace std;
#define PB push_back
#define LL long long
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORD(i,a,b) for (int i = (a); i >= (b); i--)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define st first
#define nd second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define VI vector<int>
#define PII pair<int,int>
#define LD long double

template<class C> void mini(C& a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C& a4, C b4) { a4 = max(a4, b4); }

template<class T> ostream &operator<<(ostream &os, vector<T> V){
  os<<"[";for(auto vv:V)os<<vv<<",";return os<<"]";
} 

template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

template<class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";}
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<"="<<h<<","; _dbg(sdbg+1, a...);
}


#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

vector<VI> computePrimeDivisors(int n) {
    vector<VI> divisors(n + 1);
    FOR(i, 2, n) {
        if (divisors[i].empty()) {
            for (int j = i; j <= n; j += i) {
                divisors[j].PB(i);
            }
        }
    }
    return divisors;
}

optional<int> get_prev(set<int>& s, int x) {
    auto it = s.find(x);
    if (it == s.begin()) return nullopt;
    return *prev(it);
}

optional<int> get_prev_2(set<int>& s, int x) {
    auto p = get_prev(s, x);
    if (!p) return nullopt;
    return get_prev(s, *p);
}

optional<int> get_next(set<int>& s, int x) {
    auto it = s.find(x);
    auto nxt = next(it);
    if (nxt == s.end()) return nullopt;
    return *nxt;
}

optional<int> get_next_2(set<int>& s, int x) {
    auto n = get_next(s, x);
    if (!n) return nullopt;
    return get_next(s, *n);
}

// [prev_2, prev, next, next_2]
array<optional<int>, 4> get_neighbours(set<int>& s, int x) {
    array<optional<int>, 4> res = {nullopt, nullopt, nullopt, nullopt};
    auto it = s.find(x);
    if (it != s.begin()) {
        auto p = prev(it);
        res[1] = *p;
        if (p != s.begin()) res[0] = *prev(p);
    }
    auto nxt = next(it);
    if (nxt != s.end()) {
        res[2] = *nxt;
        auto nxt2 = next(nxt);
        if (nxt2 != s.end()) res[3] = *nxt2;
    }
    return res;
}

struct MaxSegTree {
    int n;
    vector<PII> tree; // {value, -index} so max gives smallest index on tie

    MaxSegTree() : n(0) {}
    MaxSegTree(int n) : n(n), tree(2 * n, {0, 0}) {
        REP(i, n) tree[n + i] = {0, -i};
    }

    void update(int i, int delta) {
        int pos = n + i;
        tree[pos].st += delta;
        for (pos >>= 1; pos >= 1; pos >>= 1)
            tree[pos] = max(tree[2 * pos], tree[2 * pos + 1]);
    }

    // returns {max_value, index}
    PII query() {
        auto [val, neg_idx] = tree[1];
        return {val, -neg_idx};
    }
};

const int K = 10; // number of interesting primes to track
int cnt_replay = 0, cnt_recalc = 0, cnt_recalc_interesting = 0;
long long total_dist_scan = 0, total_replay_len = 0, total_prime_mod_alloc = 0;

struct Tracking {
    set<int> stones;
    unordered_map<int, int> distances;  // prime p -> count of distances divisible by p
    vector<VI> prime_divisors;     // prime_divisors[x] = list of prime factors of x
    unordered_map<int, unordered_map<int,int>> prime_mod; // prime_mod[p][r] = # stones with stone % p == r
    unordered_map<int, int> prime_freshness; // prime_freshness[p] = time t at which prime_mod[p] was last computed
    VI interesting;                // up to K interesting prime divisors
    VI q;                          // queries
    int t;                         // current query index (0-based)
    int n;                         // max stone value
};

int get_n(Tracking & t){
    return SZ(t.stones);
}

void add_distance(Tracking & t, int dist) {
    debug("add", dist);
    for (int p : t.prime_divisors[dist]) {
        t.distances[p]++;
    }
}

void remove_distance(Tracking & t, int dist) {
    debug("rem", dist);
    for (int p : t.prime_divisors[dist]) {
        t.distances[p]--;
        if (t.distances[p] < 0) debug("NEGATIVE", p, t.distances[p], dist);
        if (t.distances[p] == 0) t.distances.erase(p);
    }
}

void refresh_prime(Tracking & t, int p) {
    int replay_cost = t.t - t.prime_freshness[p];
    int recalc_cost = SZ(t.stones);
    if (replay_cost <= recalc_cost) {
        cnt_replay++;
        total_replay_len += t.t - t.prime_freshness[p];
        FOR(i, t.prime_freshness[p], t.t - 1) {
            int pos = abs(t.q[i]);
            int sign = (t.q[i] > 0) ? 1 : -1;
            t.prime_mod[p][pos % p] += sign;
        }
    } else {
        cnt_recalc++;
        t.prime_mod[p].clear();
        for (int s : t.stones) {
            t.prime_mod[p][s % p]++;
        }
    }
    t.prime_freshness[p] = t.t;
}

bool is_interesting(Tracking & t, int p) {
    auto it = t.distances.find(p);
    if (it == t.distances.end()) return false;
    return it->second >= get_n(t) / 4;
}

void recalc_interesting(Tracking & t) {
    cnt_recalc_interesting++;
    total_dist_scan += SZ(t.distances);
    int lb = (get_n(t) + 1) / 2; // ceil(stones/2), lower bound from p=2
    vector<PII> candidates; // {count, prime}
    for (auto& [p, cnt] : t.distances) {
        if (p > 2 && (t.n / p) < lb) continue; // can't beat p=2 lower bound
        if (cnt >= get_n(t) / 4) {
            candidates.PB({cnt, p});
        }
    }
    sort(ALL(candidates), greater<PII>());
    t.interesting.clear();
    t.interesting.PB(2);
    REP(i, min((int)K, SZ(candidates))) {
        if (candidates[i].nd != 2)
            t.interesting.PB(candidates[i].nd);
    }
    for (int p : t.interesting) {
        refresh_prime(t, p);
    }
}

void insert_stone(int x, Tracking & t) {
    t.stones.insert(x);
    auto nb = get_neighbours(t.stones, x);
    REP(i, 4) if (nb[i]) add_distance(t, abs(x - *nb[i]));
    if (nb[0] && nb[2]) remove_distance(t, *nb[2] - *nb[0]); // prev_2-next was next-nb, gone
    if (nb[1] && nb[3]) remove_distance(t, *nb[3] - *nb[1]); // prev-next_2 was next-nb, gone

    for (int p : t.interesting) {
        refresh_prime(t, p);
    }

    recalc_interesting(t);
}

void remove_stone(int x, Tracking & t) {
    auto nb = get_neighbours(t.stones, x);
    REP(i, 4) if (nb[i]) remove_distance(t, abs(x - *nb[i]));
    if (nb[0] && nb[2]) add_distance(t, *nb[2] - *nb[0]); // prev_2-next becomes next-nb
    if (nb[1] && nb[3]) add_distance(t, *nb[3] - *nb[1]); // prev-next_2 becomes next-nb

    for (int p : t.interesting) {
        refresh_prime(t, p);
    }

    t.stones.erase(x);
    recalc_interesting(t);
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, Q;
    cin >> n >> Q;
    Tracking t;
    t.n = n;
    t.q = VI(Q);
    t.t = 0;
    t.prime_divisors = computePrimeDivisors(n);

    REP(i, Q) {
        cin >> t.q[i];
    }
    REP(i, Q) {
        t.t++;
        int pos = abs(t.q[i]);
        if (t.stones.count(pos)) {
            t.q[i] = -pos; // negative = remove
            remove_stone(pos, t);
        } else {
            t.q[i] = pos; // positive = insert
            insert_stone(pos, t);
        }
        
        int ans = min((int)1, get_n(t));
        for (int p : t.interesting) {
            for (auto& [r, cnt] : t.prime_mod[p]) {
                maxi(ans, cnt);
            }
        }
        debug(i, pos, ans, t.interesting, get_n(t));
        
        VI dist_keys, dist_vals;
        for (auto& [p, cnt] : t.distances) { dist_keys.PB(p); dist_vals.PB(cnt); }
        debug(dist_keys, dist_vals);
        // if (i % 10000 == 0) {
        //     cerr << "i=" << i << " replay=" << cnt_replay << " recalc=" << cnt_recalc
        //          << " recalc_interesting=" << cnt_recalc_interesting
        //          << " total_dist_scan=" << total_dist_scan
        //          << " total_replay_len=" << total_replay_len
        //          << " dist_size=" << SZ(t.distances)
        //          << " stones=" << get_n(t) << endl;
        // }
        cout << ans << "\n";
    }

    // cerr << "replay=" << cnt_replay << " recalc=" << cnt_recalc
    //      << " recalc_interesting=" << cnt_recalc_interesting
    //      << " total_dist_scan=" << total_dist_scan
    //      << " total_replay_len=" << total_replay_len << endl;
    return 0;
}