#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 << ")"; }
DTP(o << a.st << ", " << a.nd, a.nd);
DTP(for (auto i : a) o << i << ", ", all(a));
void dump(auto... x) { (( cerr << x << ", " ), ...) << '\n'; }
#define deb(x...) cerr << setw(4) << __LINE__ << ":[" #x "]: ", dump(x)
#else
#define deb(...) 0
#endif

#define S 10'000'000
#define M 28
#define PRIMES 700'000

int D[S+1];
int compress[S+1];
int compress2[S+1];
int fast_div[S+1];
void sito() {
    D[1] = 1;
    int p = 0;
    for(int i = 2; i <= S; i++) {
        if (D[i] != 0) continue;
        D[i] = i;
        p++;
        compress[i] = p;
        for(int j = i * 2; j <= S; j += i) {
            D[j]= i;
        }
    }
    for(int i = 2; i <= S; i++) {
        int x = i;
        int d = D[i];
        while(x % d == 0)
            x /= d;
        fast_div[i] = x;
        compress2[i] = compress[d];
    }
}

bool is_prime(int x) {
    return (x != 1 && D[x] == x);
}

/// Stupid shit that keeps max multiset of integers where you can modify then by +-1
struct max_keeper {
    vi per_prime;
    vi last_change;
    // Truly keeps >= x instead of == cause why not.
    vi counts;
    int maks_;
    int current_session;
    max_keeper(){
        per_prime.resize(PRIMES+1);
        last_change.resize(PRIMES+1);
        current_session = 0;
        reset();
    };

    void reset() {
        current_session++;
        counts.clear();
        counts.pb(1e9);
        maks_ = 0;
    }

    int maks() {
        return maks_;
    }

    void change(int dist, int delta) {
        while(dist != 1) {
            int d = compress2[dist];
            dist = fast_div[dist];

            int p = 0;
            if (last_change[d] == current_session) {
                p = per_prime[d];
            } else {
                last_change[d] = current_session;
            }
            per_prime[d] = p + delta;

            if(delta > 0)
                inc(p);
            else
                dec(p);
            
        }
    }

  private:
    void inc(int x) {
        if(x+1 >= counts.size())
            counts.pb(0);
        counts[x+1]++;
        maks_ = max(maks_, x+1);
    } 

    void dec(int x) {
        counts[x]--;
        if(counts[x] == 0 && maks_ == x)
            maks_--;
    }
};

void solve() {
    mt19937 rng(69);

    int n,q;
    cin >> n >> q;
    // n = S;
    // q = 1'000'000;
    
    
    /// Only holds prios of currently inactive things to easily get next one.
    set<pii> prios_sort;

    // unordered_map<int, int> prios;
    vector<pii> prios; // who and what
    vector<int> pos_in_prios(n+1, -1);
    vector<pair<int, pair<int, max_keeper*>>> selected;
    vector<max_keeper*> keeper_buffer; /// Why bro, why :(
    for(int i = 1; i <= M; i++) keeper_buffer.pb(new max_keeper());
    auto select = [&keeper_buffer, &pos_in_prios, &prios, &selected](int x) {
        auto* keeper = keeper_buffer.back();
        keeper->reset();
        keeper_buffer.pop_back();

        selected.pb({prios[pos_in_prios[x]].nd, {x, keeper}});
        for(int i = (int)selected.size() - 1; i >= 1; i--) {
            if(selected[i-1].st > selected[i].st)
                swap(selected[i-1], selected[i]);
            else {
                break; 
            }
        }

        /// Add everyone >:)
        for (auto [y, p]: prios) {
            if(y == x) continue;
            int d = abs(x-y);
            keeper->change(d, 1);
        }
    };

    auto unselect = [&keeper_buffer, &selected](int x) {
        bool found = false;
        for (int i = 0; i < (int)selected.size() - 1; i++) {
            if (selected[i].nd.st == x) found = true;
            
            if (found) swap(selected[i], selected[i+1]);
        }  

        auto* keeper = selected.back().nd.nd;
        keeper_buffer.pb(keeper);
        selected.pop_back();

        // /// Clean this fockin keeper :(
        // for (auto [y, p]: prios) {
        //     if(y == x) continue;
        //     int d = abs(x-y);
        //     keeper->change(d, -1);
        // }
    };

    // int x = 0;
    while(q--) {
        int x;
        cin >> x;
        // x++;
        
        /// Remove
        if (pos_in_prios[x] != -1) {
            int pos = pos_in_prios[x];
            int p = prios[pos].nd;

            int last_guy = prios.back().st;
            swap(pos_in_prios[x], pos_in_prios[last_guy]);
            swap(prios[pos], prios.back());
            prios.pop_back();
            pos_in_prios[x] = -1;
            
            auto it = prios_sort.find({p, x});
            if (it != prios_sort.end()) {
                prios_sort.erase(it);
            } else {
                unselect(x);
            }                

            for (int i = 0; i < (int)selected.size(); i++) {
                int d = abs(x - selected[i].nd.st);
                selected[i].nd.nd->change(d, -1);
            }

        } else {
            int pos = prios.size();
            pos_in_prios[x] = pos;
            int p = rng();
            prios.pb({x, p});

            prios_sort.insert({p, x});
            
            for (int i = 0; i < selected.size(); i++) {
                int d = abs(x - selected[i].nd.st);
                selected[i].nd.nd->change(d, 1);
            }

            if(selected.size() == M && p < selected.back().st) {
                /// Remove last guy  
                int p2 = selected.back().st;
                int y = selected.back().nd.st;

                prios_sort.insert({p2, y});
                unselect(y);
            } 
        }

        while(selected.size() < M && prios_sort.size() > 0) {
            /// Get the best guy and put it here
            auto [p, y] = *prios_sort.begin();
            prios_sort.erase({p, y});

            select(y);
        }


        int ans = 0;
        for(int i = 0; i < (int)selected.size(); i++) {
            ans = max(ans, selected[i].nd.nd->maks() + 1);
        }

        cout << ans << "\n";
    }
    /// If we have x elements active we have answer at least x/2
    /// To get something better with k, n/k >= x/2 <=> 2n/x >= k
    /// We check all k <= C already, so k > C so 2n/x > C <=> x < 2n/C
    /// If C = 5000 it is almost the same. So only if we have <= 4000 elements we check it out.

}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cout << fixed << setprecision(10);
    sito();
    solve();
}