一个字段是特色字段，当且仅当其中所有元素都出现至少两次。我们尝试用一个值来描述这一特征。我们计算一个区间中出现至少两次的颜色的出现次数之和。

对于某种颜色$c$，我们考虑相邻点对$(i,j)$（即$i,j$中间没有颜色为$c$的），它会对所有包含它的区间造成$+2$的贡献。

但是这样会重复。因此我们对于相邻的三个点$(i,j,k)$，使它对包含它的区间造成$-1$的贡献。

这样为什么是对的呢？考虑只包含两个点的区间权值为$2$是合理的，此后再增加一个点，会使权值增加$+2-1$，刚好是$+1$。

接下来我们再对每一个点赋权$-1$，即包含这个点的会有$-1$的贡献。

我们根据这个权值的定义，我们会发现一个区间的权值最大值为$0$，且当且仅当此时它不是特色子段。

现在我们要求所有区间的权值最大值。

我们从左到右扫描序列，每次扫到一个点，将所有右端点为$i$的加权区间计算。

这时候我们确定右端点为$i$，左端点造成的贡献为“所有左端点在该点之前的，且右端点在$i$之前的加权区间权值和”。我们用线段树求出它的最小值。此时我们可以得到以$i$为右端点的区间权值最大值，检验其是否为$0$即可。

总复杂度$O(Tnlogn)$。

#include<bits/stdc++.h>
using namespace std;
#define lb x&(-x)
#define ls(p) (p<<1)
#define rs(p) ((p<<1)|1)
const int mod=998244353;
int T,n,c[1010000];
int b[1010000],btt;
int EF(int x){
	int l=1,r=btt;
	while(l<r){
		int mid=((l+r)>>1);
		if(b[mid]>=x) r=mid;
		else l=mid+1;
	}return l;
}
struct QRY{
	int l,r,val;
}q[1010000];
int qtt; 
int lst[201000],llst[201000];
vector<int>vecr[201000];
const int inf=1e9;
struct Tree{
	int tl,tr,dat,add;
}tree[1010000];
void build(int p,int l,int r){
	tree[p]={l,r,0,0};
	if(l==r) return ;
	int mid=((l+r)>>1);
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
}
void down(int p){
	int z=tree[p].add;
	tree[p].add=0;
	if(z==0) return ;
	tree[ls(p)].dat+=z;
	tree[rs(p)].dat+=z;
	tree[ls(p)].add+=z;
	tree[rs(p)].add+=z;
}
void update(int p,int l,int r,int w){
	int nl=tree[p].tl,nr=tree[p].tr;
	if(l<=nl&&r>=nr){
		tree[p].dat+=w;
		tree[p].add+=w;
		return ;
	}down(p);
	int mid=((nl+nr)>>1);
	if(l<=mid) update(ls(p),l,r,w);
	if(r>mid) update(rs(p),l,r,w);
	tree[p].dat=min(tree[ls(p)].dat,tree[rs(p)].dat);
}
int ask(int p,int l,int r){
	int nl=tree[p].tl,nr=tree[p].tr;
	if(l<=nl&&r>=nr){
		return tree[p].dat;
	}down(p);
	int mid=((nl+nr)>>1),ret=inf;
	if(l<=mid) ret=min(ret,ask(ls(p),l,r));
	if(r>mid) ret=min(ret,ask(rs(p),l,r));
	return ret;
}
signed main(){
//	freopen("ex.in","r",stdin);
//	freopen("my.out","w",stdout);
//	system("fc my.out ex.out");return 0;
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n;qtt=btt=0;
		for(int i=1;i<=n;i++){
			lst[i]=llst[i]=0;
			vecr[i].clear();
		} 
		for(int i=1;i<=n;i++){
			cin>>c[i];
			b[++btt]=c[i];
		}sort(b+1,b+btt+1);
		btt=unique(b+1,b+btt+1)-b-1;
		for(int i=1;i<=n;i++){
			c[i]=EF(c[i]);
			if(lst[c[i]]){
				q[++qtt]={lst[c[i]],i,2};
			}if(llst[c[i]]){
				q[++qtt]={llst[c[i]],i,-1};
			}q[++qtt]={i,i,-1};
			llst[c[i]]=lst[c[i]];
			lst[c[i]]=i;
		}
		for(int i=1;i<=qtt;i++){
			vecr[q[i].r].push_back(i);
		}
		build(1,0,n);
		int flag=-1,sum=0;
		for(int i=1;i<=n;i++){
			for(int w:vecr[i]){
				int ql=q[w].l,qv=q[w].val;
				sum+=qv;
				update(1,ql,n,qv);
			}
			flag=max(flag,sum-ask(1,0,i-1));
			if(flag==0) break;
		}
		if(flag==0) cout<<"0\n";
		else cout<<"1\n";
	}
	return 0;
}