3077: Flag

Two integer sequences existed initially, both of them are arithmetic progressions.

Arithmetic progression is a sequence of numbers such that the difference between the consecutive terms is constant. Difference here means the second minus the first. For instance, the sequence $5, 7, 9, 11, 13, 15 . . .$ is an arithmetic progression with common difference of $2$. Note that the empty sequence and the sequence consisting of one element also can be considered as arithmetic progressions.

Elements of the first sequence are inserted between elements of the second one (and, possibly, before its first element and after its last element) without changing the order. For example, sequences [$1,2,3$] and [$6,5,4$] can produce the following resulting sequences: [$1,6,2,5,3,4$], [$1,2,3,6,5,4$]. The following sequence cannot be the result of these insertions: [$1,3,6,2,5,4$] because the order of elements in the first sequence was changed.

As an acmer with ambitious goals, Flag Qing always sets plenty of flags. This time, Flag Qing supposes that for each given sequence $A$, he can find two suitable arithmetic sequences, so that $A$ can be produced by them according to the above rules.

Now given a sequence $A$, please tell Flag Qing if he can realize his flag.

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

For each test case :

The first line contains an integer $n$($1 \leq n \leq 10^{5}$), the number of sequence $A$.

The second line contains $n$ integers $A_{i}$($1 \leq A_{i} \leq 10^{9}$), the elements of sequence $A$.

For each test case print“YES”(without quotes) if it is possible, and“NO”(without quotes) otherwise.

2
6
1 6 2 5 3 4
6
1 2 7 3 5 1

YES
NO