#1014. 等差子序列

等差子序列

题目描述

给一个 11NN 的排列 {Ai}\{A_i\},询问是否存在

$$1 \le p_1<p_2<p_3<p_4<p_5<…<p_{Len} \le N (Len \ge 3) $$

使得 Ap1,Ap2,Ap3,,ApLenAp_1,Ap_2,Ap_3,\cdots,Ap_{Len} 是一个等差序列。

输入格式

输入的第一行包含一个整数 TT,表示组数。

下接 TT 组数据,每组第一行一个整数 NN,每组第二行为一个 11NN 的排列,数字两两之间用空格隔开。

输出格式

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

2
3
1 3 2
3
3 2 1
N
Y

提示

对于后 2020 个测试点的数据,1N10000,T71 \leq N \leq10000,T\leq 7,时限 2s。

对于前 55 个测试点的数据,1N5×105,T51 \leq N \leq 5\times 10^5,T \leq 5,时限 5s。