Background

GZOI2017 D2T2

Problem Description

Given a positive integer sequence of length $N$, determine whether there exists an arithmetic progression subsequence with length at least three.

Input Format

The first line contains a positive integer $T$, indicating the number of test cases.

Then follow $T$ test cases. For each test case, the first line contains a positive integer $N$, indicating the length of the sequence. The second line contains $N$ positive integers, in order, representing the numbers in the sequence.

Output Format

For each test case, output a separate line containing YES or NO.

3
4
4 3 2 1
2
1 100
5
1 17 9 18 17

YES
NO
YES

Hint

Constraints

For $20\%$ of the testdata: $N \le 100$.

For $40\%$ of the testdata: $N \le 10^3$.

For $100\%$ of the testdata: $1 \le T \le 10$, $1 \le N \le 2 \times 10^4$, and each number in the sequence is $\le 2 \times 10^4$.

Translated by ChatGPT 5