1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

const int K_MAX = 15000;
const int N_MAX = 10000005;

int* dp_flat;
int* dp[K_MAX + 1];
int cnt_val[N_MAX + 1];
bool has_stone[N_MAX + 1];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    long long total_elements = (long long)K_MAX * (K_MAX + 1) / 2;
    dp_flat = new int[total_elements]();

    long long offset = 0;
    for (int K = 2; K <= K_MAX; ++K) {
        dp[K] = &dp_flat[offset];
        offset += K;
    }

    cnt_val[0] = total_elements;
    int max_small = 0;
    set<int> active_stones;
    int C = 0;

    for (int qi = 0; qi < q; ++qi) {
        int x;
        cin >> x;

        if (!has_stone[x]) {
            has_stone[x] = true;
            C++;
            active_stones.insert(x);

            int K = 2;
            int limit = x < K_MAX ? x : K_MAX;
            for (; K <= limit; ++K) {
                int rem = x % K;
                int v = dp[K][rem];
                cnt_val[v]--;
                v++;
                dp[K][rem] = v;
                cnt_val[v]++;
                if (v > max_small) max_small = v;
            }
            int rem = x;
            for (; K <= K_MAX; ++K) {
                int v = dp[K][rem];
                cnt_val[v]--;
                v++;
                dp[K][rem] = v;
                cnt_val[v]++;
                if (v > max_small) max_small = v;
            }
        } else {
            has_stone[x] = false;
            C--;
            active_stones.erase(x);

            int K = 2;
            int limit = x < K_MAX ? x : K_MAX;
            for (; K <= limit; ++K) {
                int rem = x % K;
                int v = dp[K][rem];
                cnt_val[v]--;
                v--;
                dp[K][rem] = v;
                cnt_val[v]++;
            }
            int rem = x;
            for (; K <= K_MAX; ++K) {
                int v = dp[K][rem];
                cnt_val[v]--;
                v--;
                dp[K][rem] = v;
                cnt_val[v]++;
            }
            if (cnt_val[max_small] == 0) max_small--;
        }

        int best = max_small;
        if (best == 0 && C > 0) best = 1;

        if (C > 0 && n / best > K_MAX) {
            for (auto it_i = active_stones.begin(); it_i != active_stones.end(); ++it_i) {
                int S_i = *it_i;
                int K_limit = (n - S_i) / best;
                if (K_limit <= K_MAX) continue;

                int max_S_j = S_i + K_limit;
                auto it_end = active_stones.upper_bound(max_S_j);

                if (it_end != active_stones.begin()) {
                    auto it_j = it_end;
                    --it_j;
                    while (true) {
                        if (it_j == it_i) break;
                        int S_j = *it_j;
                        int K = S_j - S_i;
                        if (K <= K_MAX) break;

                        long long target = (long long)S_i + (long long)best * K;
                        if (target <= n && has_stone[target]) {
                            if (!(S_i - K >= 1 && has_stone[S_i - K])) {
                                int len = 2;
                                int curr = S_j + K;
                                while (curr <= n && has_stone[curr]) {
                                    len++;
                                    curr += K;
                                }
                                if (len > best) best = len;
                            }
                        }
                        if (it_j == active_stones.begin()) break;
                        --it_j;
                    }
                }
            }
        }
        cout << best << "\n";
    }

    return 0;
}