就是线段树+hash的普通思路

#include<bits/stdc++.h>
#define int long long
#define F(i,a,b) for(int i=a;i<=b;i++)
#define R(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=2e6+7;
const int mod=1e9+7;
const int base=131;
int n,a[N],bas[N];
mt19937_64 e(time(0));
struct SGT{
	int val,val2,len;
}t[N];
inline void pushup(int k){
	t[k].val=t[k<<1].val*bas[t[k<<1|1].len]+t[k<<1|1].val;
	t[k].val2=t[k<<1|1].val2*bas[t[k<<1].len]+t[k<<1].val2;
	t[k].val%=mod;
	t[k].val2%=mod;
}
inline void build_tree(int l,int r,int k){
	t[k].len=r-l+1;
	if(l==r){
		t[k].val=0;
		t[k].val2=0;
		return ;
	}
	int mid=(l+r)>>1;
	build_tree(l,mid,k<<1);
	build_tree(mid+1,r,k<<1|1);
	pushup(k);
}
inline void update(int now_l,int now_r,int pos,int k){
	if(now_l==now_r){
		t[k].val=1;
		t[k].val2=1;
		return ;
	}
	int mid=(now_l+now_r)>>1;
	if(pos<=mid) update(now_l,mid,pos,k<<1);
	else update(mid+1,now_r,pos,k<<1|1);
	pushup(k);
}
inline int query(int now_l,int now_r,int l,int r,int k){
	if(l<=now_l&&r>=now_r){
		return t[k].val;
	}
	int mid=(now_l+now_r)>>1,ans=0;
	if(r<=mid){
		ans=query(now_l,mid,l,r,k<<1);
		ans%=mod;
	} 
	else if(l>mid){
		ans=query(mid+1,now_r,l,r,k<<1|1);
		ans%=mod;
	}
	else{
		ans=query(now_l,mid,l,r,k<<1)*bas[r-mid]+query(mid+1,now_r,l,r,k<<1|1);
		ans%=mod;
	}
	pushup(k);
	return ans;
}
inline int query2(int now_l,int now_r,int l,int r,int k){
	if(l<=now_l&&r>=now_r){
		return t[k].val2;
	}
	int mid=(now_l+now_r)>>1,ans=0;
	if(r<=mid){
		ans=query2(now_l,mid,l,r,k<<1);
		ans%=mod;
	} 
	else if(l>mid){
		ans=query2(mid+1,now_r,l,r,k<<1|1);
		ans%=mod;
	}
	else{
		ans=query2(mid+1,now_r,l,r,k<<1|1)*bas[mid-l+1]+query2(now_l,mid,l,r,k<<1);
		ans%=mod;
	}
	pushup(k);
	return ans;
}
signed main(){
	int T;
	cin>>T;
	bas[0]=1;
	F(i,1,500000){
		bas[i]=bas[i-1]*base;
		bas[i]%=mod;
	}
	while(T--){
		bool thy=true;
		cin>>n;
		F(i,1,n){
			cin>>a[i];
		}
		build_tree(1,n,1);
		int val1=0,val2=0;
		F(i,1,n){
			int sz=min(a[i]-1,n-a[i]);
	//		cout<<"a[i]:"<<a[i]<<"\n";
	//		cout<<sz<<"\n";
			if(a[i]!=1&&a[i]!=n) val1=query(1,n,a[i]-sz,a[i]-1,1);
			if(a[i]!=1&&a[i]!=n) val2=query2(1,n,a[i]+1,a[i]+sz,1);
			update(1,n,a[i],1);
	//		cout<<val1<<" "<<val2<<"\n";
	//		F(j,1,n){
	//			cout<<query(1,n,j,j,1)<<" ";
	//		}
	//		cout<<"\n";
	//		F(j,1,n){
	//			cout<<query2(1,n,j,j,1)<<" ";
	//		}
	//		cout<<"\n";
			if(a[i]==1||a[i]==n) continue;
			if(val1!=val2){
				puts("Y");
				thy=false;
				break;
			}
		}
		if(thy)puts("N");
	}
	return 0;
}