#include <bits/stdc++.h>
using namespace std;

const int INPUT_SIZE = 1000010;
const int NUMBER_SIZE = 1000010;

bool is_composite[NUMBER_SIZE];
vector<int> big_factors[NUMBER_SIZE];

int n;
int q;

// If there are less stones than this, we switch to low-stone mode
const int THRESHOLD_L = 4000;
// If there are more than this, we switch to high-stone mode
const int THRESHOLD_H = 8000;

// Threshold for a prime to be small
// For primes larger than this the result is always < 2000
const int SMALL_PRIME = 501;;
vector<int> small_primes;

// 
int small_prime_results[2300][SMALL_PRIME];

// When we update an element, add it here
// When we want the current result, pop until we get a valid one
// We probably want a separate queue for big and small results?
set<pair<int, pair<int, int>>> h_results;
set<pair<int, pair<int, int>>> l_results;

void update_small_primes(int pos, bool stone) {
	int delta;
	if (stone) {
		delta = -1;
	}
	else {
		delta = 1;
	}

	for (int i = 0; i < small_primes.size(); i++) {
		int mod = pos % small_primes[i];
		if (small_prime_results[i][mod] >= 3) {
			h_results.erase(make_pair(small_prime_results[i][mod], make_pair(i, mod)));
		}
		small_prime_results[i][mod] += delta;
		if (small_prime_results[i][mod] >= 3) {
			h_results.insert(make_pair(small_prime_results[i][mod], make_pair(i, mod)));
		}
	}
}

// Holds all stones -- always up to date
set<int> all_stones;

// Holds results for all big primes, only up to date if in low mode
map<pair<int, int>, int> big_prime_results;

void update_big_primes(int pos, bool stone) {
	set<pair<int, int>> visited;
	for (auto it = all_stones.begin(); it != all_stones.end(); it++) {
		int delta = (*it) - pos;
		if (delta < 0) {
			delta = -delta;
		}

		int change;
		if (stone) {
			change = -1;
		}
		else {
			change = 1;
		}

		for (int j = 0; j < big_factors[delta].size(); j++) {
			int prime = big_factors[delta][j];
			int mod = pos % prime;
			auto pair = make_pair(prime, mod);
			if (!visited.contains(pair)) {
				visited.insert(pair);
				int x = big_prime_results[pair];
				if (x >= 3) {
					l_results.erase(make_pair(x, pair));
				}
				x += change;
				if (x == 1) {
					x+=change;
				}
				if (x > 0) {
					big_prime_results[pair] = x; // I can remove 1 access here
				}
				else {
					big_prime_results.erase(pair); 
				}
				if (x >= 3) {
					l_results.insert(make_pair(x, pair));
				}
			}
		}
	}
}

void update_big_primes_2(int pos) {
	for (auto it = all_stones.begin(); it != all_stones.end(); it++) {
		int delta = (*it) - pos;
		if (delta < 0) {
			delta = -delta;
		}

		int change = 1;
		set<pair<int, int>> visited;

		for (int j = 0; j < big_factors[delta].size(); j++) {
			int prime = big_factors[delta][j];
			int mod = pos % prime;
			auto pair = make_pair(prime, mod);
			if (!visited.contains(pair)) {
				visited.insert(pair);
				int x = big_prime_results[pair];
				l_results.erase(make_pair(x, pair));
				x += change;
				if (x > 0) {
					big_prime_results[pair] = x; // I can remove 1 access here
				}
				else {
					big_prime_results.erase(pair); 
				}
				if (x >= 3) {
					l_results.insert(make_pair(x, pair));
				}
			}
		}
	}
}


void sito_run() {
	for (int i = 2; i < NUMBER_SIZE; i++) {
		if (!is_composite[i]) {
			if (i <= SMALL_PRIME) {
				small_primes.push_back(i);
				int j = i;
				while (j < NUMBER_SIZE) {
					is_composite[j] = true;
					j += i;
				}
			}
			else {
				int j = i;
				while (j < NUMBER_SIZE) {
					is_composite[j] = true;
					big_factors[j].push_back(i);
					j += i;
				}
			}
		}
	}
}

bool stones[INPUT_SIZE];

bool high_mode = false;

void switch_to_low_mode() {
	high_mode = false;
	// Update all data

	//cerr << "Switching to low" << endl;
	
	big_prime_results.clear();
	for (auto it = all_stones.begin(); it != all_stones.end(); it++) {
		update_big_primes_2(*it);
	}

	//cerr << "Switched" << endl;

}

void switch_to_high_mode() {
	l_results.clear();
	high_mode = true;
	// The high mode data is always up to date -- maybe unnecessarily so?
}
/*
bool is_h_top_valid() {
	auto x = h_results.top();
	int res = x.first;
	int prime_id = x.second.first;
	int mod = x.second.second;
	return small_prime_results[prime_id][mod] == res;
}*/

int get_h_result() {
/*
	while (!h_results.empty() && !is_h_top_valid()) {
		h_results.pop();
	}*/

	if (h_results.empty()) {
		return 0;
	}
	auto x = h_results.rbegin();
	return (*x).first;
}
/*

bool is_l_top_valid() {
	auto x = l_results.top();
	int res = x.first;
	auto pair = x.second;
	return big_prime_results[pair] == res;
}*/

int get_l_result() {

	/*while (!l_results.empty() && !is_l_top_valid()) {
		l_results.pop();
	}*/

	if (l_results.empty()) {
		return 0;
	}
	auto x = l_results.rbegin();
	return (*x).first;
}


int main() {
	std::ios_base::sync_with_stdio(false);
	
	sito_run();

	cin >> n;
	cin >> q;

	int stone_count = 0;

	for (int i = 0; i < q; i++) {
		int pos;
		cin >> pos;
		pos -= 1;

		if (stones[pos]) {
			stone_count -= 1;
			if (stone_count <= THRESHOLD_L && high_mode) {
				switch_to_low_mode();
			}
		}
		else {
			stone_count += 1;
			if (stone_count >= THRESHOLD_H && !high_mode) {
				switch_to_high_mode();
			}
		}
		//cerr << "Doing small primes update" << endl;
		update_small_primes(pos, stones[pos]);
		//cerr << "Done" << endl;
		if (!high_mode) {
			//cerr << "Doing big primes update" << endl;
			update_big_primes(pos, stones[pos]);
			//cerr << "Done" << endl;
		}
		//cerr << h_results.size() << endl;
		if (stones[pos]) {
			all_stones.erase(pos);
		}
		else {
			all_stones.insert(pos);
		}
		stones[pos] = !stones[pos];
		//cerr << "Calc res" << endl;
		int r1 = get_h_result();
		int r2 = get_l_result();
		int res = max(r1, r2);
		if (stone_count >= 1) {
			res = max(res, 1);
		}
		if (stone_count >= 2) {
			res = max(res, 2);
		}
		//cerr << "H_results: " << h_results.size() << endl;
		cout << res << "\n";
	}
}