#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

const int large_prime_threshold = 500;
inline bool is_large_prime(int x) {
	return x >= large_prime_threshold;
}

vi smallest_prime_factor;
vi all_primes;

void build_sieve(int n) {
	smallest_prime_factor.resize(n + 1, 0);
	fwd(value, 2, n + 1) {
		if (smallest_prime_factor[value] == 0) {
			smallest_prime_factor[value] = value;
			all_primes.push_back(value);
		}
		if (!is_large_prime(smallest_prime_factor[value])) {
			smallest_prime_factor[value] =
				smallest_prime_factor[value / smallest_prime_factor[value]];
		}
		for (int prime : all_primes) {
			if (value * prime > n) {
				break;
			}
			smallest_prime_factor[value * prime] = prime;
			if (value % prime == 0) {
				break;
			}
		}
	}
}

// tracks all small primes
struct small_prime_solver {
	small_prime_solver(int q) : count_tally(q + 1, 0) {
		for (int prime : all_primes) {
			if (is_large_prime(prime)) {
				break;
			}
			small_primes.push_back(prime);
			residue_counts.emplace_back(array<int, large_prime_threshold>{});
		}
		count_tally[0] = 1e9;
	}
	vi small_primes;
	vector<array<int, large_prime_threshold> > residue_counts;
	vi count_tally;
	int max_count = 0;
	template<bool add>
	int modify(int x) {
		rep(i, sz(small_primes)) {
			int prime = small_primes[i];
			int residue = x % prime;
			int &count = residue_counts[i][residue];
			if constexpr (add) {
				count_tally[count]--;
				count_tally[count + 1]++;
				if (count == max_count) {
					max_count++;
				}
				count++;

			} else {
				count_tally[count]--;
				count_tally[count - 1]++;
				if (count_tally[max_count] == 0) {
					max_count--;
				}
				count--;
			}
		}
		return max_count;
	}
};

const int fraction_top = 2;
const int fraction_bottom = 3;
// since ans >= k / 2, it's enough to find components of size
// >= (k / 2) * fraction
// changing fraction changes how often we need to update the whole solver
// larger fraction -> more recomps, but higher probabilities
const int random_samples = 300;

// brutal check better for small sets
const int brutal_check_threshold = 10;

set<int> value_set;

template<bool add>
inline void modify_value_set(int x) {
	if constexpr (add) {
		value_set.insert(x);
	} else {
		value_set.erase(x);
	}
}

// perhaps change the map to
// a vector if we get better bounds on the number
// of different keys
// or consider gp maps
struct brutal_solver {
	const static int count_bound =
		brutal_check_threshold * brutal_check_threshold;
	brutal_solver() : count_tally(count_bound + 1, 0) {
		count_tally[0] = 1e9;
	}
	// take whole value set
	// expects set to be updated before calling
	// add parameter not needed
	map<ll, int> size_counts;
	vi count_tally;
	int max_count = 0;
	// value_set must be non-empty
	int calc_result() {
		int result = 1;
		int pair_num = 0;
		while (pair_num + result <= max_count) {
			pair_num += result;
			result++;
		}
		return result;
	}
	int recompute() {
		fill(all(count_tally), 0);
		count_tally[0] = 1e9;
		max_count = 0;
		size_counts.clear();
		set<int> cur_vals = value_set;
		value_set.clear();
		for (int x : cur_vals) {
			// calc result gets wasted inside
			// but maybe not bad for performance
			modify<true>(x);
			value_set.insert(x);
		}
		if (value_set.empty()) {
			return 0;
		}
		return calc_result();
	}
	// expects set to be not updated before calling
	// i.e. previous state of the set
	template<bool add>
	int modify(int x) {
		for (int y : value_set) {
			int diff = abs(x - y);
			int last_prime = -1;
			while (int prime = smallest_prime_factor[diff]) {
				if (prime != last_prime) {
					last_prime = prime;
					int residue = x % prime;
					ll hash_prime_residue = ((1LL * prime) << 32LL) | residue;
					int &count = size_counts[hash_prime_residue];
					if constexpr (add) {
						count_tally[count]--;
						count_tally[count + 1]++;
						if (count == max_count) {
							max_count++;
						}
						count++;
					} else {
						count_tally[count]--;
						count_tally[count - 1]++;
						if (count_tally[max_count] == 0) {
							max_count--;
						}
						if (count-- == 1) {
							size_counts.erase(hash_prime_residue);
						}
					}
				}
				diff /= prime;
			}
		}
		if (sz(value_set) == 1 && !add) {
			return 0;
		}
		return calc_result();
	}
};

// tracks large primes that can be the maximum at some point
// large prime solver is responsible for updating the value set
// so its easier for him internally
mt19937 rng(1126799);
struct large_prime_solver {
	// take whole value set
	// expects set to be updated before calling
	// add parameter not needed
	// {prime, residue, count}
	vector<array<int, 3> > residue_counts;
	int amortized_recomp() {
		vi value_set_vec(all(value_set));
		vector<pii> residues;
		int large_set_threshold =
			(fraction_top * sz(value_set)) / (fraction_bottom * 2);
		rep(_, random_samples) {
			int x = value_set_vec[rng() % sz(value_set_vec)];
			int y = x;
			while (x == y) {
				y = value_set_vec[rng() % sz(value_set_vec)];
			}
			int diff = abs(x - y);
			int last_prime = -1;
			while (int prime = smallest_prime_factor[diff]) {
				if (prime != last_prime) {
					last_prime = prime;
					int gens_at_most = sz(smallest_prime_factor) / prime + 1;
					if (gens_at_most >= large_set_threshold) {
						int residue = x % prime;
						residues.push_back({prime, residue});
					}
				}
				diff /= prime;
			}
		}
		sort(all(residues));
		residues.erase(unique(all(residues)), residues.end());
		residue_counts.clear();
		int max_count = 0;
		for (auto &[prime, residue] : residues) {
			int count = 0;
			for (int x : value_set) {
				if (x % prime == residue) {
					count++;
				}
			}
			if (count >= large_set_threshold) {
				residue_counts.push_back({prime, residue, count});
			}
			if (count > max_count) {
				max_count = count;
			}
		}

		potential_dangerous_max_count = large_set_threshold - 1;
		return max_count;
	}
	// value set state agnostic
	// so we dont care about its state
	template<bool add>
	int amortized_modify(int x) {
		int new_max_count = 0;
		for (auto &[prime, residue, count] : residue_counts) {
			if (x % prime == residue) {
				if constexpr (add) {
					count++;
				} else {
					count--;
				}
			}
			if (count > new_max_count) {
				new_max_count = count;
			}
		}
		return new_max_count;
	}
	template<bool add>
	int modify(int x, int small_primes_result) {
		// was previously in brutal
		if (potential_dangerous_max_count == -1) {
			bool operation_jumps_from_small_to_large =
				add && (int(value_set.size()) == brutal_check_threshold);
			if (operation_jumps_from_small_to_large) {
				modify_value_set<add>(x);
				return amortized_recomp();
			}
			int result = brutal.modify<add>(x);
			modify_value_set<add>(x);
			return result;
		}
		// was not in brutal
		int current_max_count = amortized_modify<add>(x);
		if constexpr (add) {
			potential_dangerous_max_count++;
		}
		modify_value_set<add>(x);
		if (potential_dangerous_max_count >
			max(small_primes_result, current_max_count)) {
			if (sz(value_set) <= brutal_check_threshold) {
				potential_dangerous_max_count = -1;
				return brutal.recompute();
			}
			return amortized_recomp();
		}

		return current_max_count;
	}
	int potential_dangerous_max_count = -1;
	// -1 if the last query was not amortized, otherwise
	// the number of amortized steps left
	brutal_solver brutal; // framemog
};

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, q;
	cin >> n >> q;
	build_sieve(n + 1);
	small_prime_solver small_primes(q);
	large_prime_solver large_primes;
	rep(i, q) {
		int x;
		cin >> x;
		if (value_set.count(x)) {
			int small_result = small_primes.modify<false>(x);
			int large_result = large_primes.modify<false>(x, small_result);
			int result = 0;
			result = max(result, small_result);
			result = max(result, large_result);
			cout << result << '\n';
		} else {
			int small_result = small_primes.modify<true>(x);
			int large_result = large_primes.modify<true>(x, small_result);
			int result = 0;
			result = max(result, small_result);
			result = max(result, large_result);
			cout << result << '\n';
		}
	}
#ifdef LOCF
	cout.flush();
	cerr << "- - - - - - - - -\n";
	(void)!system(
		"grep VmPeak /proc/$PPID/status | sed s/....kB/\' MB\'/1 >&2"); // 4x.kB
																		// ....kB
#endif
	return 0;
}