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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second

const int MAXS = 447;
int prime[MAXS]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163};

const int P = 200;
const int MAXP = prime[P-1];

class DynamicSet{
    public:
    vector<int> pos;
    vector<int> array;
    int dyn_length;
    int max_size;
    DynamicSet(int max_size = 0){ init(max_size); };
    void init(int max_size_){
        max_size = max_size_;
        dyn_length = -1;
        pos.assign(max_size, -1);
        array.assign(max_size, 0);
    }
    void add_value(int a){
        if( pos[a] != -1 ) return;
        array[ ++dyn_length ] = a;
        pos[a] = dyn_length;
    }
    void remove_value(int a){
        if( pos[a] == -1 ) return;
        pos[ array[ dyn_length ] ] = pos[a];
        swap( array[ dyn_length ], array[ pos[a] ] );
        array[ dyn_length-- ] = 0;
        pos[a] = -1;
    }
    pair<int, int> return_random_pair(){
        if( dyn_length <= 1 ) return {-1, -1};
        return {array[rand()%(dyn_length+1)], array[rand()%(dyn_length+1)]}; 
    }
    void modify(int a, int change){
        if( change == 0 ) remove_value(a);
        else              add_value(a);
    }
};

class SegmentTree{
    public:
    int n, S;
    vector<int> tree;
    SegmentTree( int n = 0 ){ init(n); };
    void init(int n_){
        n = n_;
        S = 2;
        while( S < n ) S*=2;
        tree.assign(2*S, 0);
    }
    void update(int pos, int val){
        assert(0 <= pos && pos < n);
        pos += S;
        tree[pos] += val;
        while( pos > 1 ){
            pos /= 2;
            tree[pos] = max(tree[pos*2], tree[pos*2+1]);
        }
    }
    int global_max(){
        return tree[1];
    }
};

class KlasyPro{
    public:
    int n;
    vector<int> klasy;
    vector< SegmentTree >small_primes;
    DynamicSet DS;
    KlasyPro(int n = 0){ init(n); };
    void init(int n_){
        n = n_;
        klasy.assign(n+1, 0);
        small_primes.assign(P, SegmentTree());
        for(int i = 0; i < P; i++) small_primes[i] = SegmentTree( prime[i] );
        DS.init(n+1);
    }
    void update_klasy_and_dynamic_set(int a){
        int change = (klasy[a] == 0);
        klasy[a] = change;
        DS.modify(a, change);
        for(int i = 0 ; i < P; i++){
            if( change == 1 ) small_primes[i].update( a%prime[i], 1);
            else              small_primes[i].update( a%prime[i], -1);
        }
    }

    int iterate_over_small_primes(){
        int res = (DS.dyn_length >= 0);
        for(int i = 0 ; i < P; i++){
            if( (n+prime[i]-1)/prime[i] < res ) return res;
            res = max(res, small_primes[i].global_max());
        }
        return res;
    }

    int compute_max_prime(int number){
        if( number == 0 ) return 1;
        for(int i = 0; i < (MAXS+1)/2; i++){
            while( number%prime[i] == 0 ) number/=prime[i];
            while( number%prime[MAXS-i-1] == 0 ) number/=prime[MAXS-i-1];
            if( number == 1 ) return number;
        }
        return number;
    }

    int compute_big_jumps(int p1, int jump){
        int suma = 0;
        for(int i = p1; i >= 1; i-=jump) suma+=klasy[i];
        for(int i = p1+jump; i <= n; i+=jump) suma+=klasy[i];
        return suma;
    }

    int compute_big_result(int max_small){
        int res = 0;
        if( (n+MAXP-1)/MAXP <= max_small ){
            return 0;
        }
        for(int i = 0; i <= 15; i++){
            pair<int,int> r_p = DS.return_random_pair();
            int jump = compute_max_prime( abs(r_p.f - r_p.s) );
            if( jump <= 1 ) continue;
            res = max(res, compute_big_jumps(r_p.f, jump) );
        }
        return res;
    }

    int answer_query(int a){
        update_klasy_and_dynamic_set(a);
      //  cout << "START " << a << endl;
        int small_result = iterate_over_small_primes();
      //  cout << "small " << small_result << endl;
        int big_result = compute_big_result(small_result);
        return max(small_result, big_result);
    }
};

void solve(){
    int n, t; int a;
    cin >> n >> t;
    KlasyPro KP(n);
    for(int i = 1; i <= t; i++){
        cin >> a;
        cout << KP.answer_query(a) << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    srand( clock() );
    solve();
    return 0;
}