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
#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> sieve(int n) {

    std::vector<bool> primes(n + 1, true);
    primes[0] = primes[1] = false;
    std::vector<int> res;
    for (int i = 2; i * i <= n; i++)
        if (primes[i])
            for (int j = i * i; j <= n; j += i)
                primes[j] = false;
    for (int i = 2; i <= n; ++i)
        if (primes[i])
            res.push_back(i);
    return res;
}

struct max_tree_t
{
    int p;
    std::vector<int> max;

    void init(int n)
    {
        p = 1;
        while (p < n)
            p *= 2;
        max.resize(p * 2, 0);
    }

    int get_max() const { return max[1]; }

    void add(int pos, int value)
    {
        pos += p;
        max[pos] += value;
        update(pos);
    }

private:
    void update(int pos)
    {
        pos /= 2;
        while (pos >= 1)
        {
            max[pos] = std::max(max[pos * 2], max[pos * 2 + 1]);
            pos /= 2;
        }
    }
};

int main()
{
    int n, q;
    std::cin >> n >> q;

    std::vector<bool> a(n, false);
    std::vector<int> pos(q);
    int max_d = 0;
    int d = 0;
    for (int i = 0; i < q; ++i)
    {
        int p;
        std::cin >> p;
        --p;
        const int inc = (a[p] = !a[p]) ? 1 : -1;
        d += inc;
        if (d > max_d)
            max_d = d;
        pos[i] = p;
    }
    a.clear();
    a.resize(n, false);

    std::vector<max_tree_t> mod_prime_counters;
    const int max_prime = n;// std::min(n, (2 * n + max_d - 1) / max_d);
    const std::vector<int> primes = sieve(max_prime);
    int max_prime_count = 0;
    while (max_prime_count < primes.size() && primes[max_prime_count] <= max_prime)
        ++max_prime_count;
    mod_prime_counters.resize(max_prime_count);
    for (int prime_index = 0; prime_index < max_prime_count; ++prime_index)
        mod_prime_counters[prime_index].init(primes[prime_index]);

    for (int i = 0; i < q; ++i)
    {
        const int p = pos[i];
        const int inc = (a[p] = !a[p]) ? 1 : -1;
        int max_jumps = 0;
        for (int prime_index = 0; prime_index < max_prime_count; ++prime_index)
        {
            const int prime = primes[prime_index];
            mod_prime_counters[prime_index].add(p % prime, inc);
            max_jumps = std::max(max_jumps, mod_prime_counters[prime_index].get_max());
        }
        std::cout << max_jumps << std::endl;
    }

    return 0;
}

/*

9 10
1
4
8
2
3
8
6
9
2
4

*/