可以设 $f_{i,j}(i>j)$ 表示当前序列的最后两个数分别是 $a_j,a_i$ 的答案，枚举 $i,j$ 后对每个 $i$ 做一个全局最大值和次大值即可做到 $O(n^2)$，这个东西状态数就满了，看起来很没前途。

设答案下标序列为 $b$，注意到 $(b_i,b_{i+1})$ 之间只能有不超过 $4$ 种与 $b_i,b_{i+1}$ 均不相同的颜色出现。证明很简单，如果有 $5$ 种及以上的颜色，那么必然可以在 $b_i$ 和 $b_{i+1}$ 中间再插入一个数。

所以有效状态只有 $O(nk)$ 个，其中 $k=2$，直接 $O(nk)$ 或 $O(nk^2)$ 计算即可，下面这份实现是 $O(nk^2)$ 的。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int B=4;//事实上可以要求 b_i 要离 b_{i+1} 尽可能近，所以只能有 3 种颜色
int t,m,a[200005],f[200005][B],lst[200005][B];
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>t;
	while(t--){
		cin>>m;
		int n=0;
		for(int i=1;i<=m;i++){
			cin>>a[i];
			if(a[i]!=a[n]) a[++n]=a[i];
		}
		for(int i=1;i<=n;i++){
			lst[i][0]=i-1;
			for(int j=1,k=0;j<B;k++)
				if(a[lst[i-1][k]]!=a[i])
					lst[i][j++]=lst[i-1][k];
		}
		for(int i=1;i<=n;i++)
			for(int j=0;j<B;j++){
				f[i][j]=0;
				for(int k=0;k<B;k++)
					if(a[i]!=a[lst[lst[i][j]][k]])
						f[i][j]=max(f[i][j],f[lst[i][j]][k]);
				f[i][j]++;
			}
		int ans=0;
		for(int i=1;i<=n;i++) 
			for(int j=0;j<B;j++)
				ans=max(ans,f[i][j]);
		cout<<ans<<'\n';
	}
	return 0;
}