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
#include <cstdio>
#include <map>
#include <vector>
#include <set>

int N;

std::vector<int> generuj_pierwsze(int max)
{
  std::vector<bool> P(max+1, true);
  std::vector<int> pierwsze;
  pierwsze.reserve(664579);

  P[0] = P[1] = false;
  for (int p=2; p<=N; ++p) {
    if (P[p]) {
      pierwsze.push_back(p);
      int n = p;
      while ((n += p) <= N) {
        P[n] = false;
      }
    }
  }
  return pierwsze;
}

std::map<int,int> kamienie_modulo[664579];
std::multiset<int> kamienie_wyniki[664579];

std::set<int> kamienie;

int main()
{
  int Q;
  scanf("%d%d", &N, &Q);

  std::vector<int> pierwsze = generuj_pierwsze(std::max(N, 2));
  const int NP = pierwsze.size();
  
  std::vector<int> max_kamieni(NP);
  for (int ip=0; ip<NP; ++ip) {
    max_kamieni[ip] = 2 * N / pierwsze[ip];
  }
  int lastP = NP - 1;

  int ileK = 0;
  std::vector<bool> K(N+1, false);

  while (Q-->0) {
    int a; scanf("%d", &a);
    K[a] = !K[a];
    if (K[a]) {
      ++ileK;
      kamienie.insert(a);
      // tu może wylecieć ostatnia liczba pierwsza
      while (lastP > 0 && max_kamieni[lastP] < ileK) {
        kamienie_modulo[lastP].clear();
        kamienie_wyniki[lastP].clear();
        --lastP;
      }
    } else {
      --ileK;
      // tu możemy musieć przeliczyć na nowo kolejną liczbę pierwszą
      while (lastP < NP - 1 && max_kamieni[lastP + 1] >= ileK) {
        ++lastP;
        int p = pierwsze[lastP];
        for (int a : kamienie) {
          int ap = a % p;
          kamienie_modulo[lastP][ap]++;
        }
        for (auto& pair : kamienie_modulo[lastP]) {
          kamienie_wyniki[lastP].insert(pair.second);
        }
      }
      kamienie.erase(a);
    }
    int max = 0;
    for (int ip=0; ip<=lastP; ++ip) {
      int p = pierwsze[ip];
      int ap = a % p;
      if (K[a]) {
        // położenie kamienia
        int nowy_wynik = ++kamienie_modulo[ip][ap];
        if (nowy_wynik != 1) {
          kamienie_wyniki[ip].erase(kamienie_wyniki[ip].find(nowy_wynik - 1));
        } 
        kamienie_wyniki[ip].insert(nowy_wynik);
      } else {
        // zabranie kamienia
        int stary_wynik = kamienie_modulo[ip][ap];
        kamienie_wyniki[ip].erase(kamienie_wyniki[ip].find(stary_wynik));
        if (stary_wynik == 1) {
          kamienie_modulo[ip].erase(ap);
        } else {
          kamienie_modulo[ip][ap]--;
          kamienie_wyniki[ip].insert(stary_wynik - 1);
        }
      }
      if (!kamienie_wyniki[ip].empty()) {
        max = std::max(max, *kamienie_wyniki[ip].rbegin());
      }
    }
    printf("%d\n", max);
  }
}