Description

Given a permutation $\{A_i\}$ of $1$ to $N$, determine whether there exist indices

$$1 \le p_1 < p_2 < p_3 < p_4 < p_5 < \cdots < p_{Len} \le N, \quad Len \ge 3,$$

such that $A_{p_1}, A_{p_2}, A_{p_3}, \cdots, A_{p_{Len}}$ form an arithmetic progression.

Input Format

The first line contains an integer $T$, the number of test cases.

Then follow $T$ test cases. For each test case, the first line contains an integer $N$, and the second line contains a permutation of $1$ to $N$, with numbers separated by single spaces.

Output Format

For each test case, output a single line with Y if there exists an arithmetic subsequence, otherwise output N.

2
3
1 3 2
3
3 2 1

N
Y

Hint

For the first $5$ test points, $1 \leq N \leq 5 \times 10^5$, $T \leq 5$, time limit $5$ s.

For the remaining $21$ test points, $1 \leq N \leq 10000$, $T \leq 7$, time limit $2$ s.

Translated by ChatGPT 5