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
import sys
import random

def solve():
    d = sys.stdin.read().split()
    if not d: return
    
    N = int(d[0])
    queries = [int(x) for x in d[2:]]
    
    LPF = [0] * (N + 1)
    for i in range(2, N + 1):
        if LPF[i] == 0:
            for j in range(i, N + 1, i):
                LPF[j] = i
                
    P_small = [i for i in range(2, min(N + 1, 3163)) if LPF[i] == i]
    num_P = len(P_small)
    
    offset = [0] * num_P
    curr_off = 0
    for i in range(num_P):
        offset[i] = curr_off
        curr_off += P_small[i]
        
    counts = [0] * curr_off
    freq = [[0] * (N // p + 2) for p in P_small]
    for i, p in enumerate(P_small):
        freq[i][0] = p
        
    max_f = [0] * num_P
    has_st = bytearray(N + 1)
    pos = [0] * (N + 1)
    active = []
    out = []
    
    for x in queries:
        if has_st[x]:
            has_st[x] = 0
            idx = pos[x]
            last = active[-1]
            active[idx] = last
            pos[last] = idx
            active.pop()
            
            for i in range(num_P):
                idx_c = offset[i] + (x % P_small[i])
                c = counts[idx_c]
                counts[idx_c] -= 1
                freq[i][c] -= 1
                freq[i][c - 1] += 1
                if c == max_f[i] and freq[i][c] == 0:
                    max_f[i] -= 1
        else:
            has_st[x] = 1
            active.append(x)
            pos[x] = len(active) - 1
            
            for i in range(num_P):
                idx_c = offset[i] + (x % P_small[i])
                c = counts[idx_c]
                counts[idx_c] += 1
                freq[i][c] -= 1
                freq[i][c + 1] += 1
                if c + 1 > max_f[i]:
                    max_f[i] = c + 1
                    
        M = len(active)
        if M <= 1:
            out.append(str(M))
            continue
            
        ans = max(max_f)
        if ans >= 3162:
            out.append(str(ans))
            continue
            
        sample = active if M <= 30 else random.sample(active, 30)
        thresh = 1 if M <= 30 else 3
        cand = {}
        
        for i in range(len(sample)):
            for j in range(i + 1, len(sample)):
                p = LPF[abs(sample[i] - sample[j])]
                if p > 3162:
                    r = sample[i] % p
                    cand[(p, r)] = cand.get((p, r), 0) + 1
                    
        for (p, r), v in cand.items():
            if v >= thresh:
                if N // p >= M:
                    c = sum(1 for s in active if s % p == r)
                else:
                    c = sum(1 for curr in range(r or p, N + 1, p) if has_st[curr])
                if c > ans: ans = c
                    
        out.append(str(ans))
        
    sys.stdout.write('\n'.join(out) + '\n')

solve()