Description：

给一个 $1$ 到 $N$ 的排列 $\{A_i\}$ ，询问 $A_i$ 是否存在一个等差子序列。

$N\le 10000,T\le 7$

Solution：

只要找到长为 $3$ 的等差数列即可，也就是要找到 $i<j<k$ ,使得 $a[j]-a[i]=a[k]-a[j]$ ；

我们考虑按顺序插入 $a[]$ ，对于我们当前位置 $j$ ，如果有一个 $a[i]$ 已经出现了，但是 $a[k]$ 还没有出现，因为是排列，所以这个 $a[k]$ 必然在后面,所以答案为 $'Y'$ ；

我们用一个辅助数组 $b[]$ ，按顺序如果 $x$ 出现了，就标记为 $1$ ，那么如果一个数 $x$ 满足条件，那么必然有 $b[x-y]\ne b[x+y]$ ,那么只需要判断以 $x$ 为中心的最长的字符串是否为回文串即可；

因为如果不是回文串那么必然能找到一个 $b[x-y]\ne b[x+y]$ ，所以答案为 $'Y'$ ，判断回文串可以用正反两边哈希，然后哈希值要动态修改，所以用树状数组和线段树都可以；

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 10010

int n;

int a[MAXN];

typedef long long ll;

ll power[MAXN];

struct node

{

	int lc,rc;

	ll hash1,hash2;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

#define mod 1000000007ll

#define base 3 

void build(int &rt,int l,int r)

{

	rt = newnode();

	t[rt].lc = t[rt].rc = 0;t[rt].hash1 = t[rt].hash2 = 0ll;

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void add(int rt,int p,int l,int r)

{

	if(l == r)

	{

		t[rt].hash1 = t[rt].hash2 = 1;

		return;

	}

	if(p <= mid)add(t[rt].lc,p,l,mid);

	else add(t[rt].rc,p,mid + 1,r);

	t[rt].hash1 = (t[t[rt].lc].hash1 + power[mid - l + 1] * t[t[rt].rc].hash1 % mod) % mod;

	t[rt].hash2 = (t[t[rt].rc].hash2 + power[r - mid] * t[t[rt].lc].hash2 % mod) % mod;

	return;

}

ll query1(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)

	{

		return t[rt].hash1;

	}

	if(R <= mid)return query1(t[rt].lc,L,R,l,mid);

	if(L >= mid + 1)return query1(t[rt].rc,L,R,mid + 1,r);

	return (query1(t[rt].lc,L,R,l,mid) + power[min(mid - l + 1,mid - L + 1)] * query1(t[rt].rc,L,R,mid + 1,r) % mod) % mod;

}

ll query2(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)

	{

		return t[rt].hash2;

	}

	if(R <= mid)return query2(t[rt].lc,L,R,l,mid);

	if(L >= mid + 1)return query2(t[rt].rc,L,R,mid + 1,r);

	return (query2(t[rt].rc,L,R,mid + 1,r) + power[min(R - mid,r - mid)] * query2(t[rt].lc,L,R,l,mid) % mod) % mod;

}

void work()

{

	ptr = 0;

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

		scanf("%d",&a[i]);

	build(root,1,n);

	for(int i = 1;i <= n;++i)

	{

		add(root,a[i],1,n);

		int l = min(a[i],n - a[i] + 1);//cout << a[i] - l + 1 << " " << a[i] << " " << query1(root,a[i] - l + 1,a[i],1,n) << " " << a[i] << " " << a[i] + l - 1 << " " << query2(root,a[i],a[i] + l - 1,1,n) << endl;

		if(l > 1 && query1(root,a[i] - l + 1,a[i],1,n) != query2(root,a[i],a[i] + l - 1,1,n))

		{

			printf("Y\n");

			return;

		}

	}

	printf("N\n");

	return;

}

int main()

{

	power[0] = 1;

	for(int i = 1;i < MAXN;++i)power[i] = power[i - 1] * base % mod;

	int testcases;

	scanf("%d",&testcases);

	for(int i = 1;i <= testcases;++i)

		work();

	return 0;

}