A. Interesting Subsequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given an sequence $$$a$$$ of size $$$n$$$.

Determine if there is a sequence $$$b$$$ that satisfies all the following conditions:

  • $$$b$$$ is a subsequence of $$$a$$$;
  • There's an index $$$i(1\leq i \leq n)$$$,if we note $$$c=\underbrace{[[a_1,...a_{i-1},a_{i+1},...,a_n],[a_1,...a_{i-1},a_{i+1},...,a_n],...,[a_1,...a_{i-1},a_{i+1},...,a_n]]}_{n\cdot (n-1)elements}$$$,$$$b$$$ is not a subsequence of $$$c$$$.

A subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. For example,$$$[1,2]$$$ and $$$[1,1]$$$ are subsequences of $$$[1,2,1]$$$ but $$$[2,2]$$$ and $$$[3]$$$ are not.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 2\cdot 10^5$$$).

The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

If there is a sequence $$$b$$$ that satisfies all the following conditions output YES.Otherwise,output NO.

Example
Input
3
2
1 2
2
1 1
6
4 1 5 4 1 1
Output
YES
NO
YES
Note

Test Case $$$1$$$:

$$$b=[1]$$$ is one of valid sequence.For index $$$i=1$$$,note $$$c=[a_2,a_2]=[2,2]$$$,then $$$b$$$ is not a subsequence of $$$c$$$.

Test Case $$$2$$$:

For index $$$i=1,2$$$,$$$c=[1,1]$$$ always holds.No matter which subsequence $$$b$$$ of $$$a$$$ you choose, $$$b$$$ must be a subsequence of $$$c$$$.