记录编号	584835	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2011]等差子序列	最终得分	100
用户昵称	ムラサメ	是否通过	通过
代码语言	C++	运行时间	0.702 s
提交时间	2023-11-16 13:14:27	内存使用	7.84 MiB

#include<bits/stdc++.h>
#define mod 1145141919
typedef long long ll;
using namespace std;
struct node{
	long long l,r,sum;
}t[2][40010];
long long tt,n,a[10010];
long long ps[5][10010],md,l1,r1,l2,r2,len,ans,num1,num2;
long long bas[10010];
bool flag;
void build(long long i,long long l,long long r,bool ff){
	t[ff][i].l=l;
	t[ff][i].r=r;
	t[ff][i].sum=0;
	if(l==r){
		ps[ff][l]=i;
		t[ff][i].sum=0;
		return;
	}	
	long long mid=(l+r)>>1;
	build(i*2,l,mid,ff);
	build(i*2+1,mid+1,r,ff);
}
void find(ll i,ll l,ll r,ll ff){
	if(l<=t[ff][i].r&&r>=t[ff][i].l){
		if(l<=t[ff][i].l&&r>=t[ff][i].r){
			ans=(ans+t[ff][i].sum*bas[r-t[ff][i].r])%mod;
			return;
		}
		find(i*2,l,r,ff);
		find(i*2+1,l,r,ff);
	}	
}
void change(ll x,ll ff){
	ll now=ps[ff][x];
	t[ff][now].sum=1;
	while(now/2!=0){
		now/=2;
		t[ff][now].sum=(t[ff][now*2].sum*bas[t[ff][now*2+1].r-t[ff][now*2+1].l+1]+t[ff][now*2+1].sum)%mod;
	}
}
void work(){
	memset(t,0,sizeof(t));
	memset(a,0,sizeof(a));
	memset(ps,0,sizeof(ps));
	memset(bas,0,sizeof(bas));
	bas[0]=1;
	for(int i=1;i<=300005;++i){
		bas[i]=bas[i-1]*2%mod;
	}
	cin>>n;
	flag=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n,0);
	build(1,1,n,1);
	for(int i=1;i<=n;i++){
		md=a[i];	
		len=min(a[i]-1,n-a[i]);
		l1=a[i]-len;
		r1=a[i]+len;
		len=2*len+1;
		ans=0;
		find(1,l1,r1,0);
		num1=ans;
		r2=n+1-l1;
		l2=n+1-r1;
		ans=0;
		find(1,l2,r2,1);num2=ans;
		if(num1!=num2){
			flag=1;
			break;
		}
		change(md,0);
		change(n-md+1,1);
	}
	if(flag){
		cout<<"Y"<<endl;
	}
	else{
		cout<<"N"<<endl;
	}
}
int main(){
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	for(int i=1;i<=t;i++){
		work();
	}
	return 0;
}