#include <bits/stdc++.h>

using namespace std;
using LL = long long;
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
#define ssize(x) int(x.size())

template<class A, class B> auto &operator<<(ostream &o, pair<A, B> p) {
    return o << '(' << p.first << ", " << p.second << ')';
}

template<class T> auto operator<<(ostream &o, T x) -> decltype(x.end(), o) {
    o << '{'; int i = 0; for (auto e : x) o << (", ")+2*!i++ << e;
    return o << '}';
}

#ifdef DEBUG
#define debug(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n';
#else
#define debug(...) {}
#endif


constexpr int MAXN = 10'000'003;
constexpr int INF = 2'000'000'013;
constexpr int PRIMES = 665'000;
constexpr int POWER = 2 << 20;
constexpr int A = 40;

// int seed = 13;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
// mt19937 rng(seed);

bool present[MAXN];
vector<int> rocks;
int rock_idx[MAXN];

int divs[MAXN];
int jump_div[MAXN];
int prime_idx[MAXN];
int prime_prep[MAXN];
int score[A * PRIMES];
int touched[A * PRIMES];
vector<int> cnt_score[A];
int best[A];
int witness_tag[A];

int tree[2 * POWER];
int leaf_index[2 * POWER];
int tree_reindex[MAXN];

vector<pair<int, int>> witness;
int witness_place[A];
vector<int> free_indices;


void fill_primes() {
    int total_primes = 0;
    FOR(i, 2, MAXN - 1) {
        if (divs[i] != 0)
            continue;
        prime_idx[i] = total_primes;
        total_primes++;
        for (int j = i; j < MAXN; j += i)
            divs[j] = i;
    }

    int x, prev_x;
    FOR(i, 2, MAXN - 1) {
        prev_x = x = i;
        prime_prep[x] = prime_idx[divs[x]];
        while (x > 1) {
            x /= divs[x];
            if (divs[x] != divs[prev_x]) {
                jump_div[prev_x] = x;
                prev_x = x;
            }
        }
    }
}


void set_value(int x, int val) {
    x += POWER - 1;
    tree[x] = val;
    x /= 2;
    while (x > 0) {
        tree[x] = max(tree[x * 2], tree[x * 2 + 1]);
        if (tree[x * 2] >= tree[x * 2 + 1])
            leaf_index[x] = leaf_index[x * 2];
        else
            leaf_index[x] = leaf_index[x * 2 + 1];
        x /= 2;
    }
}


void update_witness_score(int wit_idx, int p_idx, bool removed) {
    int wp_idx = wit_idx * PRIMES + p_idx;

    if (touched[wp_idx] != witness_tag[wit_idx]) {
        touched[wp_idx] = witness_tag[wit_idx];
        score[wp_idx] = 0;
    }

    int old_score = score[wp_idx];
    if (old_score > 0)
        cnt_score[wit_idx][old_score]--;
    if (removed) {
        if (old_score > 0 && cnt_score[wit_idx][old_score] == 0 && best[wit_idx] == old_score)
            best[wit_idx]--;
        score[wp_idx]--;
    }
    else {
        if (best[wit_idx] == old_score)
            best[wit_idx]++;
        score[wp_idx]++;
    }

    int new_score = score[wp_idx];
    if (new_score > 0) {
        if (new_score == ssize(cnt_score[wit_idx]))
            cnt_score[wit_idx].emplace_back(0);
        cnt_score[wit_idx][new_score]++;
    }
}

void new_witness(int x, int prio, int prev_idx) {
    int wit_idx, y;
    if (prev_idx != -1) {
        swap(witness.back(), witness[prev_idx]);
        wit_idx = witness.back().second;
        witness.pop_back();
    }
    else {
        wit_idx = free_indices.back();
        free_indices.pop_back();
    }
    witness.emplace_back(prio, wit_idx);

    best[wit_idx] = 0;
    cnt_score[wit_idx].clear();
    cnt_score[wit_idx].emplace_back(0);
    witness_tag[wit_idx]++;
    witness_place[wit_idx] = x;
    for (const auto &j: rocks) {
        y = abs(x - j);
        while (y > 1) {
            update_witness_score(wit_idx, prime_prep[y], false);
            y = jump_div[y];
        }
    }
}

void update_witnesses_remove(int x) {
    int ans = 0, repeat_idx = -1, y;
    int wit_place, wit_idx, leaf;

    for (int j = 0; j < ssize(witness); j++) {
        wit_idx = witness[j].second;
        wit_place = witness_place[wit_idx];
        if (wit_place == x) {
            repeat_idx = j;
            continue;
        }

        y = abs(x - wit_place);
        while (y > 1) {
            update_witness_score(wit_idx, prime_prep[y], true);
            y = jump_div[y];
        }

        if (best[wit_idx] > ans)
            ans = best[wit_idx];
    }

    leaf = leaf_index[1];
    if (repeat_idx != -1 && tree[1] > 0) {
        new_witness(leaf, tree[1], repeat_idx);
        ans = max(ans, best[witness.back().second]);
        set_value(tree_reindex[leaf], 0);
    }
    else if (repeat_idx != -1) {
        free_indices.emplace_back(witness[repeat_idx].second);
        swap(witness.back(), witness[repeat_idx]);
        witness.pop_back();
    }
    else {
        set_value(tree_reindex[x], 0);
    }

    if (witness.empty())
        cout << "0\n";
    else
        cout << ans + 1 << '\n';
}


void update_witnesses_insert(int x) {
    int ans = 0, prio, mx_prio = 0, mx_prio_idx, y;
    int wit_place, wit_idx;
    bool added = false;

    for (int j = 0; j < ssize(witness); j++) {
        if (witness[j].first > mx_prio) {
            mx_prio = witness[j].first;
            mx_prio_idx = j;
        }
        wit_idx = witness[j].second;
        wit_place = witness_place[wit_idx];

        y = abs(x - wit_place);
        while (y > 1) {
            update_witness_score(wit_idx, prime_prep[y], false);
            y = jump_div[y];
        }

        if (best[wit_idx] > ans)
            ans = best[wit_idx];
    }

    prio = rng() % INF + 1;
    if (ssize(witness) < A) {
        new_witness(x, prio, -1);
        added = true;
    }
    else if (prio < mx_prio) {
        wit_idx = witness[mx_prio_idx].second;
        set_value(tree_reindex[witness_place[wit_idx]], mx_prio);
        new_witness(x, prio, mx_prio_idx);
        added = true;
    }
    if (!added)
        set_value(tree_reindex[x], prio);
    else
        ans = max(ans, best[witness.back().second]);

    cout << ans + 1 << '\n';
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    fill_primes();

    for (int i = A - 1; i >= 0; i--)
        free_indices.emplace_back(i);

    int n, q, x;
    int idx, used_in_tree = 0;
    cin >> n >> q;
    rocks.reserve(q);
    while (q--) {
        cin >> x;
        if (present[x]) {
            present[x] = false;
            idx = rock_idx[x];
            rocks[idx] = rocks.back();
            rock_idx[rocks.back()] = idx;
            rocks.pop_back();
            update_witnesses_remove(x);
        }
        else {
            used_in_tree++;
            tree_reindex[x] = used_in_tree;
            leaf_index[used_in_tree + POWER - 1] = x;
            present[x] = true;
            rock_idx[x] = ssize(rocks);
            rocks.emplace_back(x);
            update_witnesses_insert(x);
        }
    }

    return 0;
}