#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 10000005;

int cnt[3165][3165];
int freq_B[MAXN];
int freq_K[MAXN];
int last_seen[MAXN];
int list_K[MAXN];
int count_len[MAXN];
int stones[MAXN];
int temp_stones[MAXN];
int spf[MAXN];
bool A[MAXN];
int divs[500];

int N, Q;
int B, MAX_P;
int max_B = 0;
int max_gt_B = 0;
bool maintain_k_gt_B = true;
int num_stones = 0;
int query_id = 0;
int threshold_stones;

void sieve() {
    for (int i = 1; i < MAXN; i++) spf[i] = i;
    for (int i = 2; i * i < MAXN; i++) {
        if (spf[i] == i) {
            for (int j = i * i; j < MAXN; j += i) {
                if (spf[j] == j) spf[j] = i;
            }
        }
    }
}

void recompute_gt_B() {
    memset(count_len, 0, sizeof(int) * (MAX_P + 5));
    max_gt_B = 0;
    
    int saved_num = num_stones;
    for (int i = 0; i < saved_num; ++i) temp_stones[i] = stones[i];
    num_stones = 0;
    
    for (int i = 0; i < saved_num; ++i) {
        int x = temp_stones[i];
        query_id++;
        int num_list = 0;
        for (int j = 0; j < num_stones; ++j) {
            int y = stones[j];
            int D = abs(x - y);
            int temp = D;
            int n_divs = 1;
            divs[0] = 1;
            while (temp > 1) {
                int p = spf[temp];
                int count = 0;
                while (temp % p == 0) {
                    count++;
                    temp /= p;
                }
                int cur_num = n_divs;
                long long multiplier = p;
                for (int k = 1; k <= count; ++k) {
                    for (int l = 0; l < cur_num; ++l) {
                        divs[n_divs++] = divs[l] * multiplier;
                    }
                    multiplier *= p;
                }
            }
            for (int j_div = 0; j_div < n_divs; ++j_div) {
                int K = divs[j_div];
                if (K > B) {
                    if (last_seen[K] != query_id) {
                        last_seen[K] = query_id;
                        freq_K[K] = 0;
                        list_K[num_list++] = K;
                    }
                    freq_K[K]++;
                }
            }
        }
        for (int j_list = 0; j_list < num_list; ++j_list) {
            int K = list_K[j_list];
            int c = freq_K[K];
            if (c >= 2) count_len[c]--;
            count_len[c + 1]++;
            if (c + 1 > max_gt_B) max_gt_B = c + 1;
        }
        stones[num_stones++] = x;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    sieve();
    
    if (!(cin >> N >> Q)) return 0;
    
    B = max(2, (int)sqrt(N));
    MAX_P = (N - 1) / (B + 1) + 1;
    threshold_stones = MAX_P * 3; 
    
    freq_B[0] = 10000000; 
    
    for (int q = 0; q < Q; ++q) {
        int x;
        cin >> x;
        bool is_add = !A[x];
        
        if (is_add) {
            for (int k = 2; k <= B; ++k) {
                int s = x % k;
                int v = cnt[k][s];
                freq_B[v]--;
                cnt[k][s] = v + 1;
                freq_B[v + 1]++;
                if (v + 1 > max_B) max_B = v + 1;
            }
            
            if (num_stones + 1 > threshold_stones) maintain_k_gt_B = false;
            
            if (maintain_k_gt_B) {
                query_id++;
                int num_list = 0;
                for (int i = 0; i < num_stones; ++i) {
                    int y = stones[i];
                    int D = abs(x - y);
                    int temp = D;
                    int n_divs = 1;
                    divs[0] = 1;
                    while (temp > 1) {
                        int p = spf[temp];
                        int count = 0;
                        while (temp % p == 0) { count++; temp /= p; }
                        int cur_num = n_divs;
                        long long multiplier = p;
                        for (int k = 1; k <= count; ++k) {
                            for (int l = 0; l < cur_num; ++l) {
                                divs[n_divs++] = divs[l] * multiplier;
                            }
                            multiplier *= p;
                        }
                    }
                    for (int j = 0; j < n_divs; ++j) {
                        int K = divs[j];
                        if (K > B) {
                            if (last_seen[K] != query_id) {
                                last_seen[K] = query_id;
                                freq_K[K] = 0;
                                list_K[num_list++] = K;
                            }
                            freq_K[K]++;
                        }
                    }
                }
                for (int i = 0; i < num_list; ++i) {
                    int K = list_K[i];
                    int c = freq_K[K];
                    if (c >= 2) count_len[c]--;
                    count_len[c + 1]++;
                    if (c + 1 > max_gt_B) max_gt_B = c + 1;
                }
                stones[num_stones++] = x;
                A[x] = true;
            } else {
                stones[num_stones++] = x;
                A[x] = true;
            }
        } else {
            for (int k = 2; k <= B; ++k) {
                int s = x % k;
                int v = cnt[k][s];
                freq_B[v]--;
                cnt[k][s] = v - 1;
                freq_B[v - 1]++;
                if (v == max_B && freq_B[max_B] == 0) max_B--;
            }
            
            if (maintain_k_gt_B) {
                A[x] = false;
                for (int i = 0; i < num_stones; ++i) {
                    if (stones[i] == x) {
                        stones[i] = stones[num_stones - 1];
                        num_stones--;
                        break;
                    }
                }
                query_id++;
                int num_list = 0;
                for (int i = 0; i < num_stones; ++i) {
                    int y = stones[i];
                    int D = abs(x - y);
                    int temp = D;
                    int n_divs = 1;
                    divs[0] = 1;
                    while (temp > 1) {
                        int p = spf[temp];
                        int count = 0;
                        while (temp % p == 0) { count++; temp /= p; }
                        int cur_num = n_divs;
                        long long multiplier = p;
                        for (int k = 1; k <= count; ++k) {
                            for (int l = 0; l < cur_num; ++l) {
                                divs[n_divs++] = divs[l] * multiplier;
                            }
                            multiplier *= p;
                        }
                    }
                    for (int j = 0; j < n_divs; ++j) {
                        int K = divs[j];
                        if (K > B) {
                            if (last_seen[K] != query_id) {
                                last_seen[K] = query_id;
                                freq_K[K] = 0;
                                list_K[num_list++] = K;
                            }
                            freq_K[K]++;
                        }
                    }
                }
                for (int i = 0; i < num_list; ++i) {
                    int K = list_K[i];
                    int c = freq_K[K];
                    count_len[c + 1]--;
                    if (c >= 2) count_len[c]++;
                }
                while (max_gt_B >= 2 && count_len[max_gt_B] == 0) max_gt_B--;
            } else {
                A[x] = false;
                for (int i = 0; i < num_stones; ++i) {
                    if (stones[i] == x) {
                        stones[i] = stones[num_stones - 1];
                        num_stones--;
                        break;
                    }
                }
            }
            
            if (!maintain_k_gt_B && max_B < MAX_P) {
                maintain_k_gt_B = true;
                recompute_gt_B();
            }
        }
        
        int ans = max_B;
        if (maintain_k_gt_B && max_gt_B > ans) ans = max_gt_B;
        cout << ans << "\n";
    }
    
    return 0;
}