Existence of an Arithmetic Progression in a Permutation

Given a permutation ({A_i}) of the integers from (1) to (N), determine whether there exists a subsequence with indices (1 \le p_1 < p_2 < \cdots < p_{\text{Len}} \le N) (with (\text{Len} \ge 3)) such that the sequence (A_{p_1}, A_{p_2}, \ldots, A_{p_{\text{Len}}}) forms an arithmetic progression. In other words, check if there exist indices (p_1, p_2, p_3, \ldots, p_{\text{Len}}) (with (\text{Len}\ge3)) satisfying

[ A_{p_2} - A_{p_1} = A_{p_3} - A_{p_2} = \cdots = A_{p_{\text{Len}}} - A_{p_{\text{Len}-1}}, ]

and output 1 if such a subsequence exists, or 0 otherwise.

inputFormat

The input consists of multiple test cases. The first line contains an integer (T) denoting the number of test cases. Each test case is described by two lines:

1. The first line contains an integer (N), the size of the permutation.
2. The second line contains (N) space-separated integers representing the permutation (A_1, A_2, \dots, A_N).

outputFormat

For each test case, output a single line containing 1 if there exists a subsequence of length at least three forming an arithmetic progression, or 0 otherwise.

sample

3
5
1 3 5 4 2
3
3 1 2
4
4 1 3 2

1
0
1