#ifdef LOC
#include "debuglib.hpp"
#else
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define deb(...)
#define DBP(...)
#endif
using namespace std;
using   ll         = long long;
using   vi         = vector<int>;
using   pii        = pair<int, int>;
#define pb           push_back
#define mp           make_pair
#define x            first
#define y            second
#define rep(i, b, e) for (int i = (b); i < (e); i++)
#define each(a, x)   for (auto& a : (x))
#define all(x)       (x).begin(), (x).end()
#define sz(x)        int((x).size())

struct FastMod {
	uint32_t b, m;
	FastMod(uint32_t a) : b(a), m(-1U / a) {}
	friend int operator%(int a, FastMod f) { // a % b
		uint32_t ret = uint32_t(a) - uint32_t((uint64_t(f.m)*uint32_t(a))>>32) * f.b;
		return int(ret < f.b ? ret : ret-f.b);
	}
};

constexpr int MAX_N = int(1e7) + 5;
constexpr int MAX_Q = int(1e6) + 5;
constexpr int SMALL_K = 290;
constexpr int MAX_COMMON = 3;

struct Chain {
	int k, r, cnt;
	DBP(k, r, cnt);
	bool operator==(const Chain& c) const {
		return k == c.k && r == c.r;
	}
};

mt19937_64 rng(928485030);

vector<FastMod> primes;
array<int, 2> largeFactors[MAX_N]; // indices of prime factors >= primes[SMALL_K]

int elemPos[MAX_N];
vi elems;

int smallAnsCnt[MAX_Q]; // [x] > 0 <=> smallAns >= x
vi smallModCnt[SMALL_K]; // [i][r] = how many r's mod primes[i]
Chain large[2]; // candidates for large k
int largeGap = -1; // gap between max untracked large candidate and answer bound
int smallAns, ans;

int scratchCnt[MAX_N];
vi dirty;

void addLarge(Chain c) {
	if (c == large[0]) {
		large[0].cnt = max(large[0].cnt, c.cnt);
	} else if (c == large[1]) {
		large[1].cnt = max(large[1].cnt, c.cnt);
		if (large[0].cnt < large[1].cnt) swap(large[0], large[1]);
	} else if (c.cnt >= large[0].cnt) {
		large[1] = large[0];
		large[0] = c;
	} else if (c.cnt > large[1].cnt) {
		large[1] = c;
	}
}

void updateLargeWith(int begin, int offset, int minSize) {
	int maxSeen = 0;
	dirty.clear();

	rep(pos, begin, sz(elems)) {
		int e = elems[pos];
		each(i, largeFactors[abs(e-offset)]) {
			if (!i) break;
			if (++scratchCnt[i] == 1) {
				dirty.pb(i);
			}
			maxSeen = max(maxSeen, scratchCnt[i]);
		}
		if (maxSeen+(sz(elems)-pos) < minSize) {
			each(i, dirty) scratchCnt[i] = 0;
			return;
		}
	}

	each(i, dirty) {
		if (scratchCnt[i]+1 >= minSize) {
			addLarge({i, offset%primes[i], scratchCnt[i]+1});
		}
		scratchCnt[i] = 0;
	}
}

void updateLarge() {
	constexpr int SAMPLES = 60;

	int minSize = (sz(elems) + MAX_COMMON*3) / 3;
	int bound = (sz(elems)+1) / 2;
	minSize = min(minSize, bound);
	largeGap = bound - minSize;
	each(c, large) c = {0, 0, 0};

	if (ll(primes[SMALL_K].b) * (minSize-1) > MAX_N) {
		return;
	}

	if (sz(elems) <= SAMPLES*2) {
		rep(i, 0, sz(elems)) {
			updateLargeWith(i, elems[i], minSize);
			if (large[1].cnt > minSize) break;
		}
	} else {
		rep(t, 0, SAMPLES) {
			int i = int(rng() % elems.size());
			updateLargeWith(0, elems[i], minSize);
			if (large[1].cnt > minSize) break;
		}
	}
}

void update(int a) {
	bool added = (elemPos[a] == -1);
	if (added) {
		int j = int(rng() % (sz(elems)+1));
		if (j < sz(elems)) {
			elemPos[elems[j]] = sz(elems);
			elems.pb(elems[j]);
			elems[j] = a;
			elemPos[a] = j;
		} else {
			elems.pb(a);
			elemPos[a] = j;
		}
	} else {
		elemPos[elems.back()] = elemPos[a];
		elems[elemPos[a]] = elems.back();
		elemPos[a] = -1;
		elems.pop_back();
	}

	if (!elems.empty()) {
		rep(t, 0, 3) {
			int i = int(rng() % sz(elems));
			int j = int(rng() % sz(elems));
			swap(elems[i], elems[j]);
			swap(elemPos[elems[i]], elemPos[elems[j]]);
		}
	}

	if (added) {
		rep(i, 0, SMALL_K) {
			int r = a % primes[i];
			smallAnsCnt[++smallModCnt[i][r]]++;
		}
	} else {
		rep(i, 0, SMALL_K) {
			int r = a % primes[i];
			smallAnsCnt[smallModCnt[i][r]--]--;
		}
	}

	largeGap -= (sz(elems) % 2 == 0);

	if (largeGap < 0) {
		updateLarge();
	} else {
		each(c, large) {
			if (c.k && a % primes[c.k] == c.r) {
				c.cnt += added ? 1 : -1;
			}
		}
	}

	while (smallAnsCnt[smallAns+1] > 0) smallAns++;
	while (smallAnsCnt[smallAns] == 0) smallAns--;
	ans = smallAns;
	each(c, large) ans = max(ans, c.cnt);
}

void sieve() {
	bitset<MAX_N> bs;
	bs.set();
	bs.reset(0);
	bs.reset(1);
	for (int i = 2; i*i < MAX_N; i++) {
		if (bs[i]) {
			for (int j = i*i; j < MAX_N; j += i) {
				bs.reset(j);
			}
		}
	}
	rep(i, 0, MAX_N) if (bs[i]) primes.pb(i);
}

void checkConstants() {
#ifdef LOC
	assert(SMALL_K > 0);
	assert(SMALL_K < sz(primes));

	ll p = primes[SMALL_K].b;
	ll common = MAX_N / (p*p) + 1; // chains with large k have little intersections
	assert(p*p*p > MAX_N); // at most two prime factors >= p
	if (common != MAX_COMMON) {
		deb(common);
		assert(0);
	}
#endif
}

int main() {
	cin.sync_with_stdio(0); cin.tie(0);

	sieve();
	checkConstants();

	for (int i = sz(primes)-1; i >= SMALL_K; i--) {
		int p = primes[i].b;
		for (int j = p; j < MAX_N; j += p) {
			each(f, largeFactors[j]) {
				if (f == 0) {
					f = i;
					break;
				}
			}
		}
	}

	smallAnsCnt[0] = 1;
	rep(i, 0, SMALL_K) {
		smallModCnt[i].resize(primes[i].b);
	}

	int n, q;
	cin >> n >> q;
	fill(elemPos, elemPos+n+1, -1);

	while (q--) {
		int a; cin >> a;
		update(a);
		cout << ans << '\n';
		// deb(sz(elems));
	}
}