首先可以看出 $m$ 取质数是不劣的。如果只对每个质数维护答案可以做到 $O(\frac{nq}{\log{n}})$。以下记 $\omega(n)$ 表示 $n$ 以内数不同质因子数量的最大值。

考虑静态问题的做法。取 $m=2$ 可以得到答案是 $\ge\frac{|S|}{2}$ 的，那么可以随机集合里的两个不同数 $a_i,a_j$，用所有 $p\mid a_i-a_j$ 计算并更新答案。可以先线性筛出每个数的最小质因子和最小质因子在这个数里的幂，然后就可以 $O(\omega(n))$ 一个数的所有不同质因子。这样一次计算的正确率是 $\frac{1}{4}$，时间一共是 $O(T|S|\omega(n))$，其中 $T$ 是随机次数。

为了保证正确率，随机次数大概是 $32$ 次左右。这样肯定 T 飞，于是考虑把随机去掉。把集合里的数分成 $4$ 个一组，然后分别在每组里枚举两个不同的数，这样一共会得到至多 $3|S|\omega(n)$ 个用于算答案的质数。对于最优解的那个 $p$，它被枚举到次数最少的情况一定是每组都恰好算到一次，也就是 $\frac{|S|}{4}$ 次。那么只要考虑枚举到次数 $\ge\frac{|S|}{4}$ 的，也就是至多有 $\frac{3|S|\omega(n)}{\frac{|S|}{4}}=12\omega(n)$ 个质数要考虑。这样算一个静态问题的答案就是 $O(|S|\omega(n))$ 的。

回到动态的问题。现在的问题变成了每次都要非常浪费时间地重构。于是考虑均摊的策略：如果当前集合大小为 $|S|$，就批量的处理后面的 $\frac{|S|}{3}$ 个修改。考虑这 $\frac{|S|}{3}$ 个修改全都是加入或删除的情况可以知道，每个时刻都存在一个最优解包含原来 $S$ 的 $\frac{|S|}{3}$ 个数。那么把上面静态问题的 $4$ 个一组改成 $6$ 个一组，可以得到至多 $15\omega(n)$ 个要考虑的质数。每次加入或删除就对这些质数修改即可。

这样就变成了每次给一个位置加 $\pm 1$，查询全局最大值。最大值每次操作后的变化也是 $\pm 1$，开一个桶就可以做到 $O(1)$ 查询和修改。

然后做完了，时间 $O(n+q(\log{q}+\omega(n)))$。其中 $q\log{q}$ 是 set 的复杂度。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
using namespace std;
const int N=1e7+5,M=1e6+5;
int n,m,tot;
int prime[N],np[N],pc[N],q[M],a[M],cp[N];
bool v[N];

set<int> Set;

vector<int> p,cc[M];

inline int read(){
	int x=0;
	char c=getchar();
	while(c<48||c>57) c=getchar();
	while(c>=48&&c<=57){
		x=(x<<3)+(x<<1)+c-48;
		c=getchar();
	}
	return x;
}

void primes(int n){
	for(int i=2;i<=n;i++){
		if(!v[i]) prime[++tot]=np[i]=pc[i]=i;
		for(int j=1;j<=tot&&prime[j]*i<=n;j++){
			v[i*prime[j]]=1;
			np[i*prime[j]]=prime[j];
			if(i%prime[j]) pc[i*prime[j]]=prime[j];
			else{
				pc[i*prime[j]]=pc[i]*prime[j];
				break;
			}
		} 
	}
}

void solve(int l,int r){
	int cnt=0;
	for(auto it=Set.begin();it!=Set.end();it++) a[++cnt]=(*it);
	if(Set.find(q[l])==Set.end()) a[++cnt]=q[l];
	p.clear();
	int mn=max(((int)Set.size()+5)/6,1);
	for(int i=1;i<=cnt;i+=6){
		for(int j=i;j<=min(cnt,i+5);j++){
			for(int k=j+1;k<=min(cnt,i+5);k++){
				int x=abs(a[k]-a[j]);
				while(x>1){
					cp[np[x]]++;
					if(cp[np[x]]==mn){
						p.push_back(np[x]);
						cc[p.size()-1].resize(np[x]);
					}
					x/=pc[x];
				}
			}
		}
	}
	for(int i=1;i<=cnt;i+=6){
		for(int j=i;j<=min(cnt,i+5);j++){
			for(int k=j+1;k<=min(cnt,i+5);k++){
				int x=abs(a[k]-a[j]);
				while(x>1){
					cp[np[x]]=0;
					x/=pc[x];
				}
			}
		}
	}
	int mx=0;
	for(auto it=Set.begin();it!=Set.end();it++){
		int x=(*it);
		for(int i=0;i<p.size();i++){
			int val=x%p[i];
			if(cc[i][val]) cp[cc[i][val]]--;
			mx=max(mx,++cc[i][val]);
			cp[cc[i][val]]++;
		}
	}
	for(int i=l;i<=r;i++){
		auto it=Set.find(q[i]);
		if(it==Set.end()){
			Set.insert(q[i]);
			for(int j=0;j<p.size();j++){
				int val=q[i]%p[j];
				if(cc[j][val]) cp[cc[j][val]]--;
				mx=max(mx,++cc[j][val]);
				cp[cc[j][val]]++;
			}
		}
		else{
			Set.erase(it);
			for(int j=0;j<p.size();j++){
				int val=q[i]%p[j];
				cp[cc[j][val]]--;
				if(cc[j][val]==mx&&!cp[cc[j][val]]) mx--;
				cc[j][val]--;
				if(cc[j][val]) cp[cc[j][val]]++;
			}
		}
		if(!Set.size()){
			puts("0");
			continue;
		}
		printf("%d\n",max(mx,1));
	}
	for(auto it=Set.begin();it!=Set.end();it++){
		int x=(*it);
		for(int i=0;i<p.size();i++){
			int val=x%p[i];
			cp[cc[i][val]]--;
			cc[i][val]--;
			if(cc[i][val]) cp[cc[i][val]]++;
		}
	}
}

int main(){
	n=read(),m=read();
	primes(n);
	for(int i=1;i<=m;i++) q[i]=read();
	bool st=1;
	int lst=0,rest;
	for(int i=1;i<=m;i++){
		if(st){
			st=0;
			rest=max((int)Set.size()/3,1);
		}
		rest--;
		if(!rest||i==m) solve(lst+1,i),lst=i,st=1;
	}
	return 0;
}