Description

给一个1到N的排列{Ai},询问是否存在1<=p1<p2<p3<p4<p5<…<pLen<=N (Len>=3),
使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。

Input

输入的第一行包含一个整数T,表示组数。
下接T组数据,每组第一行一个整数N,每组第二行为一个1到N的排列,数字两两之间用空格隔开。
N<=10000,T<=7

Output

对于每组数据,如果存在一个等差子序列,则输出一行“Y”,否则输出一行“N”。

Sample Input

2
3
1 3 2
3
3 2 1

Sample Output

N
Y

HINT

Source

利用一个i性质 因为是排列 所以 每个数字只会出现一次 因为要求长度>=3即可 所以我们直接求一下长度=3是否存在即可 我们一边做一边检查是否左右两边是回文串 就是检查数值的两边即可

一旦遇到不是回文串了说明肯定就可以满足条件了 毕竟我们i只需要三个 我枚举中间的点 然后算两边即可  具体hash可以用树状数组维护 看代码即可

 

分类: hash树状数组

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论