#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<cstdint>

using namespace std;

struct prime_data
{
    prime_data(int mod, int q) : p(mod), best(0), cnt(mod), freq(q + 1, 0)
    {
        freq[0] = mod;
    }

    int p;
    int best;
    vector<int> cnt;
    vector<unsigned short> freq;
};

struct small_state
{
    int limit;
    int answer;
    vector<prime_data> data;
    vector<unsigned short> freq;
};

struct large_state
{
    int on_limit;
    int off_limit;
    int answer;
    bool enabled;
    vector<int> freq;
    vector<int> active_pos;
    unordered_map<uint64_t, int> cnt;
};

struct toggle_state
{
    int stones;
    vector<int> values;
    vector<char> active;
    vector<int> where;
};


uint64_t make_key(int p, int r)
{
    return (((uint64_t) (uint32_t) p) << 32) | (uint32_t) r;
}

// najmniejszy dzielnik pierwszy
void build_spf(int n, vector<int>& spf, vector<int>& primes)
{
    spf.assign(n + 1, 0);

    for (int i = 2; i <= n; i++)
    {
        if (spf[i] == 0)
        {
            spf[i] = i;
            primes.push_back(i);
        }

        for (const int p : primes)
        {
            long long v = 1LL * i * p;
            if ((v > n) || (p > spf[i]))
            {
                break;
            }
            spf[v] = p;
        }
    }
}

// liczniki i maksima
void init_small(int n, int q, const vector<int>& primes, small_state& small)
{
    small.limit = min(n, 5000);
    small.answer = 0;
    small.freq.assign(q + 1, 0);

    for (const int p : primes)
    {
        if (p > small.limit)
        {
            break;
        }
        small.data.push_back(prime_data(p, q));
    }

    small.freq[0] = static_cast<unsigned short>(small.data.size());
}


void compress_values(const vector<int>& events, toggle_state& state)
{
    state.values = events;
    sort(state.values.begin(), state.values.end());
    state.values.erase(unique(state.values.begin(), state.values.end()), state.values.end());

    state.active.assign(state.values.size(), false);
    state.where.assign(state.values.size(), -1);
}

// #3 jesli roznica ma dzielnik pierwszy wiekszy od progu, to wystarczy pierwszy taki dzielnik
int get_big_prime(int d, int small_limit, const vector<int>& spf)
{
    while (d > 1)
    {
        int p = spf[d];
        if (p > small_limit)
        {
            return p;
        }
        while (d % p == 0)
        {
            d /= p;
        }
    }
    return 0;
}

// Zbieramy tylko te duze liczby pierwsze, ktore rzeczywiscie lacza x z jakims aktywnym polem.
void collect_big_primes(int x, int small_limit, const vector<int>& spf, const vector<int>& source, vector<int>& out)
{
    out.clear();
    out.reserve(source.size());

    for (const int y : source)
    {
        if (x == y)
        {
            continue;
        }

        int d = x > y ? (x - y) : (y - x);
        if (d <= small_limit)
        {
            continue;
        }

        int p = get_big_prime(d, small_limit, spf);
        if (p != 0)
        {
            out.push_back(p);
        }
    }

    sort(out.begin(), out.end());
    out.erase(unique(out.begin(), out.end()), out.end());
}

void reset_large(large_state& large)
{
    large.cnt.clear();
    fill(large.freq.begin(), large.freq.end(), 0);
    large.answer = 0;
}

// aktualizacja po dodaniu albo usunieciu kamienia
void update_small(int x, int delta, small_state& small)
{
    for (auto& data : small.data)
    {
        int before = data.best;
        int r = x % data.p;
        int old = data.cnt[r];
        int now = old + delta;

        data.freq[old]--;
        data.freq[now]++;
        data.cnt[r] = now;

        if (now > data.best)
        {
            data.best = now;
        }
        while ((data.best > 0) && (data.freq[data.best] == 0))
        {
            data.best--;
        }

        if (before != data.best)
        {
            small.freq[before]--;
            small.freq[data.best]++;
        }

        if (data.best > small.answer)
        {
            small.answer = data.best;
        }
    }

    while ((small.answer > 0) && (small.freq[small.answer] == 0))
    {
        small.answer--;
    }
}

void add_big(int x, const vector<int>& cand, large_state& large)
{
    for (const int p : cand)
    {
        uint64_t key = make_key(p, x % p);
        auto it = large.cnt.find(key);
        int old = 1;

        if (it != large.cnt.end())
        {
            old = it->second;
            large.freq[old]--;
            it->second++;
            large.freq[it->second]++;
            large.answer = max(large.answer, it->second);
        }
        else
        {
            large.cnt[key] = 2;
            large.freq[2]++;
            large.answer = max(large.answer, 2);
        }
    }
}

void remove_big(int x, const vector<int>& cand, large_state& large)
{
    for (const int p : cand)
    {
        uint64_t key = make_key(p, x % p);
        auto it = large.cnt.find(key);

        large.freq[it->second]--;
        it->second--;

        if (it->second == 1)
        {
            large.cnt.erase(it);
        }
        else
        {
            large.freq[it->second]++;
        }
    }

    while ((large.answer > 0) && (large.freq[large.answer] == 0))
    {
        large.answer--;
    }
}

// Odbudowa stanu dla duzych liczb pierwszych jest tania tylko wtedy, gdy kamieni jest malo.
void rebuild_big(int small_limit, const vector<int>& spf, large_state& large)
{
    reset_large(large);

    vector<int> built;
    vector<int> cand;
    built.reserve(large.active_pos.size());

    for (const int x : large.active_pos)
    {
        collect_big_primes(x, small_limit, spf, built, cand);
        add_big(x, cand, large);
        built.push_back(x);
    }
}

void activate(int id, toggle_state& state, large_state& large)
{
    state.where[id] = static_cast<int>(large.active_pos.size());
    large.active_pos.push_back(state.values[id]);
    state.active[id] = true;
}

void deactivate(int id, toggle_state& state, large_state& large)
{
    int pos = state.where[id];
    int last = large.active_pos.back();
    large.active_pos[pos] = last;
    large.active_pos.pop_back();
    state.active[id] = false;

    if (pos < static_cast<int>(large.active_pos.size()))    {
        int last_id = lower_bound(state.values.begin(), state.values.end(), last) - state.values.begin();
        state.where[last_id] = pos;
    }
    state.where[id] = -1;
}

int process_event(int x, const vector<int>& spf, small_state& small, large_state& large, toggle_state& state)
{
    int id = lower_bound(state.values.begin(), state.values.end(), x) - state.values.begin();
    vector<int> cand;

    if (!state.active[id])
    {
        update_small(x, 1, small);

        if (large.enabled)
        {
            collect_big_primes(x, small.limit, spf, large.active_pos, cand);
            add_big(x, cand, large);
        }

        activate(id, state, large);
        state.stones++;
    }
    else
    {
        update_small(x, -1, small);

        if (large.enabled)
        {
            collect_big_primes(x, small.limit, spf, large.active_pos, cand);
            remove_big(x, cand, large);
        }

        deactivate(id, state, large);
        state.stones--;
    }

    if (large.enabled && (state.stones > large.off_limit))
    {
        large.enabled = false;
        reset_large(large);
    }
    if (!large.enabled && (state.stones <= large.on_limit))
    {
        large.enabled = true;
        rebuild_big(small.limit, spf, large);
    }

    int answer = state.stones > 0 ? 1 : 0;
    answer = max(answer, small.answer);
    answer = max(answer, large.enabled ? large.answer : 0);
    return answer;
}

void solve(int n, int q, const vector<int>& events)
{
    vector<int> spf;
    vector<int> primes;
    small_state small;
    large_state large;
    toggle_state state;

    build_spf(n, spf, primes);
    init_small(n, q, primes, small);
    compress_values(events, state);

    int large_bound = (n / (small.limit + 1)) + 1;
    large.on_limit = 2 * large_bound;
    large.off_limit = large.on_limit + 2000;

    state.stones = 0;
    large.answer = 0;
    large.enabled = true;
    large.freq.assign(q + 1, 0);
    large.cnt.reserve(1 << 20);
    large.cnt.max_load_factor(0.7f);

    for (const int x : events)
    {
        cout << process_event(x, spf, small, large, state) << endl;
    }
}

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

    int n;
    int q;
    cin >> n >> q;

    vector<int> events(q);
    for (int i = 0; i < q; i++)
    {
        cin >> events[i];
    }

    solve(n, q, events);
    return 0;
}