You are given an array A of N positive integers.

In one operation, you can do the following:
Choose integers i and j (1 ≤ i < j ≤ N), such that A_{i} = A_{j};
For all k (i < k < j), change the value of A_{k} to A_{i}.

Find out whether A can have at most 2 distinct values after using any (possibly zero) number of operations.

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of two lines of input:
• The first line of each test case contains N - the size of the array.
• The next line contains $N integers, A_{1}, A_{2}, A_{3}, \ldots, A_{N} -$ the elements of the array.

------ Output Format ------

For each test case, print YES if A can have at most 2 distinct values after using any (possibly zero) number of operations and NO otherwise.

You may print each character of the string in uppercase or lowercase (for example, the strings YES, yEs, yes, and yeS will all be treated as identical).

------ Constraints ------

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $10^{5}$.

----- Sample Input 1 ------
4
5
5 9 5 5 5
3
1 2 3
4
1 2 1 3
4
1 2 3 1

----- Sample Output 1 ------
YES
NO
YES
YES

----- explanation 1 ------
Test case $1$: The array $A$ already has $2$ distinct elements.

Test case $2$: It is impossible to make operations such that $A$ has $2$ distinct elements.

Test case $3$: We can make an operation as:
- Choose $i = 1$ and $j = 3$. Thus, we change $A_{2}$ to $A_{1} = 1$.

The final array is $[1,1,1,3]$ which has two distinct elements.

Test case $4$: We can make an operation as:
- Choose $i = 1$ and $j = 4$. Thus, we change $A_{2}$ and $A_{3}$ to $A_{1} = 1$.

The final array is $[1,1,1,1]$ which has one distinct element.

见题面

见题面