#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <map>

using namespace std;

#define REP(x,n) for(int x=0;x<(n);++x)
#define FOREACH(x, c) for(auto x = (c).begin(); x != (c).end(); ++x)

const int SMALL_PRIMES = 1000;
const int MAX_N = 10000001;
const int MAX_Q = 1000001;
const int MAX_PRIMES = 664581;

set<int> stones;
vector<int> primes;

void calculatePrimes(int n) {
    if (n < 2) return;
    
    int size = (n / 2) + 1;
    vector<char> isPrime(size, 1);
    
    primes.reserve(MAX_PRIMES); 
    primes.push_back(2);

    int limit = sqrt(n);
    int i = 1;

    for (; (2 * i + 1) <= limit; ++i) {
        if (isPrime[i]) {
            int p = 2 * i + 1;
            primes.push_back(p);
            for (int j = (p * p - 1) / 2; j < size; j += p) {
                isPrime[j] = 0;
            }
        }
    }

    for (; i < size; ++i) {
        if (isPrime[i]) {
            primes.push_back(2 * i + 1);
        }
    }
}

int totalAdded[MAX_Q];
int history[MAX_Q];

int modulos[MAX_N];
int moduloCalculatedInIteration[MAX_N];
int iterationNo = 0;
int roundNo = 0;
int n;

struct PrimeScore {
    int score;
    int stepSize;
    int roundNo;
    int index;
    vector<int> cacheForSmallPrimes;
    int bestModulo;
};

int inline maxgain(int roundFrom, int roundTo) {
    return totalAdded[roundTo] - totalAdded[roundFrom];
}
bool cmp(const PrimeScore* a, const PrimeScore* b) {
    int maxScoreA = a->score + maxgain(a->roundNo, roundNo);
    int maxScoreB = b->score + maxgain(b->roundNo, roundNo);
    return maxScoreA != maxScoreB ? maxScoreA > maxScoreB : a->stepSize < b->stepSize;
};
multiset<PrimeScore*, decltype(cmp)*> queue(cmp);
PrimeScore scores[MAX_PRIMES];

vector<int> indicesAffected;
int recalcPrime(PrimeScore& thisScore) {
    int prime = thisScore.stepSize;

    if (thisScore.index < SMALL_PRIMES) {
        //optimized logic for small primes
        vector<int>& cache = thisScore.cacheForSmallPrimes;
        if (cache.size() == 0) {
            cache.resize(prime, 0);
        }
        bool bestModuloDecreased = false;
        
        indicesAffected.clear();
        for (int i=thisScore.roundNo; i<roundNo; ++i) {
            if (history[i]<0) {
                int value = (-history[i]) % prime;
                indicesAffected.push_back(value);
                if (value == thisScore.bestModulo) {
                    bestModuloDecreased = true;
                }
                --cache[value];
            } else {
                int value = history[i] % prime;
                indicesAffected.push_back(value);
                ++cache[value];
            }
        }
        int best = 0;
        int bestModulo = 0;
        if (bestModuloDecreased) {
            FOREACH(it, cache) {
                if (*it > best) {
                    best = *it;
                    bestModulo = it-cache.begin();
                }
            }
        } else {
            bestModulo = thisScore.bestModulo;
            best = cache[bestModulo];
            FOREACH(it, indicesAffected) {
                if (cache[*it] > best) {
                    best = cache[*it];
                    bestModulo = *it;
                }
            }
        }

        thisScore.roundNo = roundNo;
        thisScore.score = best;
        thisScore.bestModulo = bestModulo;
        return best;
    }

    ++iterationNo;
    int best=0;
    FOREACH(it, stones) {
        int modulo = *it % prime;
        int score;
        if (moduloCalculatedInIteration[modulo] != iterationNo) {
            moduloCalculatedInIteration[modulo] = iterationNo;
            score = modulos[modulo] = 1;
        } else {
            score = ++modulos[modulo];
        }
        best = max(score, best);
    }
    
    thisScore.roundNo = roundNo;
    thisScore.score = best;

    return best;
}

map<int, PrimeScore*> excluded;
int calculate(int n) {
    //fast-return cases for 0..2 stones
    if (stones.size() < 2) {
         // for 0 / 1 stones
        return stones.size();
    } else if (stones.size() == 2) {
        if (*stones.begin() + 1 == *stones.rbegin()) {
            return 1;
        } else {
            return 2;
        }
    }

    if (queue.empty()) {
        int bestScore = 0;

        FOREACH(it, primes) {
            PrimeScore& thisScore = scores[it-primes.begin()];
            thisScore.index = it-primes.begin();
            thisScore.stepSize = *it;
            int currentBest = recalcPrime(thisScore);
            queue.insert(&thisScore);

            if (currentBest > bestScore) {
                bestScore = currentBest;
            }
        }
        return bestScore;
    } else {
        PrimeScore* first;

        while ((first = *queue.begin())->roundNo != roundNo) {
            if (first->score + maxgain(first->roundNo, roundNo) > n/first->stepSize+1) {
                // skip false positive recalculation of great primes, since score can never exceed n/prime+1
                queue.erase(first);
                excluded[first->stepSize] = first;
                first->score = (n/first->stepSize+1) - maxgain(first->roundNo, roundNo);
            } else {
                auto it = queue.begin();
                recalcPrime(*first);
                if (queue.size() > 1 && !cmp(first, *(std::next(it)))) {
                    queue.erase(it);
                    queue.insert(first);
                }
            }
        }
        while (!excluded.empty() && n/excluded.begin()->first >= first->score) {
            PrimeScore* exc = excluded.begin()->second;
            recalcPrime(*exc);
            queue.insert(exc);
            excluded.erase(excluded.begin());
        }

        return first->score;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    int q,a;
    cin>>n>>q;
    calculatePrimes(n/3 + 100);

    REP(x,q) {
        ++roundNo;
        cin>>a;
        auto it = stones.find(a);
        if (it != stones.end()) {
            history[x] = -a;
            stones.erase(it);
        } else {
            history[x] = a;
            stones.insert(a);
            totalAdded[x+1] = totalAdded[x]+1;
        }
        cout << calculate(n) << endl;
    }

    return 0;
}