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
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

#ifdef LOCAL
auto operator<<(auto& o, auto x) -> decltype(x.first, o);
auto operator<<(auto& o, auto x) -> decltype(x.end(), o) {
  o << "{";
  for (int i = 0; auto y : x) o << ", " + !i++ * 2 << y;
  return o << "}"; }
auto operator<<(auto& o, auto x) -> decltype(x.first, o) {
  return o << "(" << x.first << ", " << x.second << ")"; }
void __print(auto... x) { ((cerr << x << " "), ...) << endl; }
#define debug(x...) __print("[" #x "]:", x)
#else
#define debug(...) 2137
#endif

const int N = 10'000'010;
vi d[N];
int n, q;
int a[N];
int poz[N];
int czy[N];
int odp;
int dwa[N];

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> q;
  n++;
  rep(i, 2, n) d[i].reserve(8);
  rep(i, 2, n) if (!sz(d[i])) for (int j = i; j < n; j += i) d[j].push_back(i);
  rep(i, 0, n) poz[i] = -1;
  vi s;
  auto dopisz = [&](int i) {
    int odl = abs(s[i] - s[i + 1]);
    for (int x : d[odl]) czy[x]++;
  };
  rep(i, 0, q) {
    cin >> a[i];
    if (poz[a[i]] == -1) {
      poz[a[i]] = sz(s);
      s.push_back(a[i]);
      if (sz(s) >= 2) dopisz(sz(s) - 2);
    } else {
      int p = poz[a[i]];
      poz[a[i]] = -1;
      if (p == sz(s) - 1) s.pop_back();
      else {
        swap(s[p], s[sz(s) - 1]);
        s.pop_back();
        poz[s[p]] = p;
        if (p) dopisz(p - 1);
        if (p < sz(s) - 1) dopisz(p);
      }
    }
  }
  int limit = 2e8 / q;
  vector<pii> moze;
  rep(i, 0, n) if (czy[i]) moze.push_back({-czy[i], i});
  sort(all(moze));
  if (sz(moze) > limit) moze.resize(limit);
  vi kand;
  rep(i, 0, sz(moze)) kand.push_back(moze[i].second);
  rep(i, 0, n) {
    if (sz(kand) > 2 * limit) break;
    if (czy[i]) kand.push_back(i);
  }
  sort(all(kand)); kand.resize(unique(all(kand)) - kand.begin());
  vector<unordered_map<int, int>> jeden(sz(kand));
  rep(i, 0, q) poz[a[i]] = -1;
  int teraz = 0;
  rep(i, 0, q) {
    if (poz[a[i]] == -1) {
      teraz++;
      poz[a[i]] = 0;
      rep(j, 0, sz(kand)) {
        int tu = jeden[j][a[i] % kand[j]]++;
        if (tu) dwa[tu]--;
        dwa[tu + 1]++;
      }
    } else {
      teraz--;
      poz[a[i]] = -1;
      rep(j, 0, sz(kand)) {
        int tu = jeden[j][a[i] % kand[j]]--;
        dwa[tu]--;
        if (tu - 1) dwa[tu - 1]++;
      }
    }
    while (dwa[odp + 1]) odp++;
    while (odp && !dwa[odp]) odp--;
    if (teraz) cout << max(odp, (teraz + 1) / 2) << '\n';
    else cout << 0 << '\n';
  }
}