8648: Arithmetic Subsequence

Given an integer array A=[a1,a2,…,an] of length $n$, you need to determine if there exists an integer array B=[b_1,b_2,\dots,b_n]B=[b1,b2,…,bn] such that the followings hold:

1. The array B is a rearrangement of A, i.e., there exists a permutation p=[p1,p2,…,pn] of size $n$ such that bi=api for each $1\le i\le n$.
2. The array B doesn't contain any arithmetic subsequence of length at least $3$.

A sequence C=[c1,c2,…,ck] is called an arithmetic subsequence of $B$ if and only if the followings are satisfied:

1. There exists a sequence of indices 1≤i1<i2<⋯<ik≤N, such that cj=bij for each $1\le j\le k$;
2. C forms an arithmetic progression, i.e., for each $1\le i\le k-2$, we have ci+2−ci+1=ci+1−ci.

The first line contains an integer T $1\le T\le 25$), denoting the number of test cases.

For each test case, the first line contains an integer $n(1\le n\le 5000)$, denoting the size of the array $A$.

The next line contains $n$ integers a1,a2,…,an(1≤ai≤109), denoting the elements of the array $A$.