首先注意到是排列，所以值域上每个数属于且仅属于一个等差数列。

令两个等差数列的公差为 $d1,d2$ 且 $d1\le d2$。

假设我们确定 $d1,d2$，方便观察合法等差数列的情况。

当 $d1=1$ 且 $d2=1$ 时，两个等差数列把值域分成两半。维护前缀最大最小值容易判断。

当 $d1=1$ 且 $d2\neq1$ 时，此时值域被其中一个等差数列删去中间一段，前后剩余都是公差为 $1$ 的等差数列，则要满足剩下的数能组成等差数列且公差不为 $1$，前后必然只能剩余一个数。维护前缀最大最小值容易判断。

当 $d1=2$ 时，此时值域被其中一个等差数列间隔的删去，剩余的必然也是一个公差为 $2$ 的等差数列。维护前缀奇偶性容易判断。

当 $d1>2$ 时，此时 $1$ 和 $2$ 被归入不同的等差数列作为首项，而 $3$ 无法被归入任何一个等差数列，故不存在解。

于是简单判断即可。时间复杂度 $O(n)$

分享一个用 gcd 做的方法，相对于正解来说时间复杂度会多带个 log，但是能过。

思路

假设一个数列 $A$ 能达到的最大公差为 $G$，那么加入一个数字 $m$ 后新数列的最大公差显然是 $\gcd(G,abs(m-A_i))$，其中 $A_i$ 为数列中任意一个数字。（读者自证不难）

特判一个数字的情况，然后从两个数字的情况初始化公差。

若数列 $A$ 是等差数列，那么就肯定有 $A_{min}+(len_A-1)\times G=A_{max}$。

时间复杂度 $O(n \log n)$

代码

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int inf = 0x3f3f3f3f3f;
int T,n,a[1001000],gc,tr[1001000],mx,mn,ans;
int gcd(int a,int b){
	if(!b)return a;
	return gcd(b,a%b);
}
signed main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);mx=0;mn=inf;ans=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			if(i==n)break;
			mx=max(a[i],mx);mn=min(a[i],mn);
			if(i==1){
				tr[i]++;
				continue;
			}
			if(i==2){
				tr[i]++;
				gc=mx-mn;
				continue;
			}
			gc=gcd(gc,abs(a[i]-a[1]));
			if(mn+(i-1)*gc==mx)tr[i]++;
		}
		mn=inf,mx=0;
		for(int i=n;i>=1;i--){
			if(i==1)break;
			mx=max(a[i],mx);mn=min(a[i],mn);
			if(i==n){
				tr[i-1]++;
				continue;
			}
			if(i==n-1){
				tr[i-1]++;
				gc=mx-mn;
				continue;
			}
			gc=gcd(gc,abs(a[i]-a[n]));
			if(mn+(n-i)*gc==mx)tr[i-1]++;
		}
		for(int i=1;i<n;i++){
			if(tr[i]==2)ans++;
			tr[i]=0;
			
		}
		printf("%d\n",ans);
	}
	return 0;
}