L. Median of the Array
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Define the median of an array $$$b_1, b_2, \dots b_k$$$ as $$$b_{\lfloor \frac{k + 1}{2} \rfloor}$$$ after sorting the array $$$b$$$.

For example, the median of the array $$$b = [5, 4, 6, 1, 1]$$$ is $$$4$$$ because after sorting the array becomes $$$b = [1, 1, 4, 5, 6]$$$ and $$$b_{\lfloor \frac{5 + 1}{2} \rfloor} = b_{\lfloor \frac{6}{2} \rfloor} = b_3 = 4$$$. In the same way, the median of the array $$$[3, 5, 2, 7]$$$ is $$$3$$$.

Given an array $$$a_1, a_2, \dots, a_n$$$, is it possible to divide it into two non-empty arrays $$$b$$$ and $$$c$$$ (not necessarily of the same length), such that each element of $$$a$$$ is either in $$$b$$$ or in $$$c$$$, and the medians of both $$$b$$$ and $$$c$$$ are equal?

Note: $$$\lfloor x \rfloor$$$ denotes the integer part of $$$x$$$ (e.g., $$$\lfloor 5.3 \rfloor = 5$$$ and $$$\lfloor 2.7 \rfloor = 2$$$).

Input

The first line of the input contains a single integer t ($$$1 \le t \le 10^5$$$) — the number of test cases.

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

The second line of each testcase consists of $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9)$$$.

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

Output

Output $$$t$$$ lines. For each testcase, print "YES" (without quotes) if there exists two non-empty arrays that satisfy the conditions, and print "NO"(without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive response).

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

Explanation of the first testcase:

The possible ways to divide the array $$$a$$$ into two non-empty arrays $$$b$$$ and $$$c$$$ are:

$$$b = [2]$$$, $$$c = [1]$$$

$$$b = [1]$$$, $$$c = [2]$$$

In both ways, the medians of $$$b$$$ and $$$c$$$ are not equal.

Explanation of the second testcase:

A possible way to divide the array $$$a$$$ into two non-empty arrays $$$b$$$ and $$$c$$$ is:

$$$b = [2]$$$, $$$c = [3, 2]$$$

In this case, the medians of $$$b$$$ and $$$c$$$ are equal to $$$2$$$, and remember that when calculating the median you should first sort the array. That's why, the median of $$$c$$$ is $$$2$$$.

Explanation of the third testcase:

Some possible ways to divide the array $$$a$$$ into two non-empty arrays $$$b$$$ and $$$c$$$ with equal medians are:

$$$b = [4, 9, 3, 3]$$$, $$$c = [6, 3]$$$

$$$b = [6, 4, 3, 3]$$$, $$$c = [3, 9]$$$

$$$b = [4, 3]$$$, $$$c = [6, 9, 3, 3]$$$