P2757 [CTT] Arithmetic Subsequence

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.

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.

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

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