以前缀为例，我们依次枚举 $1\sim n$。我们算出前缀最大值和前缀最小值，然后算出公差，然后暴力检查这个前缀的合法性。（其中特判公差为 $1$）。

我通过了本题，问这做法复杂度是否正确。

int n;std::cin>>n;
	ve<int>v(n+1);
	for(int i=1;i<=n;i++)
		std::cin>>v[i];
	bool flg=true;
	for(int i=1;i<=n;i++)
		if(v[i]!=i){
			flg=false;
			break;
		}
	if(flg)return std::cout<<n-1<<'\n',void();
	int ans=0;
	int mn=1e9,mx=0,d=0;
	ve<int>pre(n+1),suf(n+1);
	ve<int>vis(n+1);
	for(int i=1;i<=n;i++){
		mx=std::max(mx,v[i]);
		mn=std::min(mn,v[i]);
		vis[v[i]]=true; 
		if(i>1&&(mx-mn)%(i-1)==0){
			int d=(mx-mn)/(i-1);
			if(d==1){pre[i]=true;continue;}
			bool flg=true;
			for(int k=mn;k<=mx;k+=d)
				if(!vis[k]){
					flg=false;
					break;
				}
			pre[i]=flg;
		}else if(i==1)pre[i]=true;
	}mn=1e9,mx=0;
	for(int i=1;i<=n;i++)vis[i]=0;
	for(int i=n;i>=1;i--){
		mx=std::max(mx,v[i]);
		mn=std::min(mn,v[i]);
		vis[v[i]]=true; 
		if(i<n&&(mx-mn)%(n-i)==0){
			int d=(mx-mn)/(n-i);
			if(d==1){suf[i]=true;continue;}
			bool flg=true;
			for(int k=mn;k<=mx;k+=d)
				if(!vis[k]){
					flg=false;
					break;
				}
			suf[i]=flg;
		}else if(i==n)suf[i]=true;
	}
	for(int i=1;i<n;i++)
		ans+=pre[i]&&suf[i+1];
	std::cout<<ans<<'\n';