题目描述

时间限制：$1$ 秒
内存限制：$256$ 兆字节

给定一个整数数组 $a_1, a_2, \ldots, a_n$。你可以进行以下操作任意多次（包括零次）：

• 选择一个下标 $i$（$1 \leq i \leq n$），将 $a_i$ 乘以 $-1$（即更新 $a_i := -a_i$）。

你的任务是判断是否可以通过进行任意次上述操作，使得位于下标 $1$ 的元素成为数组的中位数。注意，操作也可以应用于下标 $1$，这意味着中位数可以是 $a_1$ 的原始值或其相反数。

数组 $b_1, b_2, \ldots, b_m$ 的中位数定义为数组 $b$ 中第 $\lceil \frac{m}{2} \rceil$ 小的元素。例如，数组 $[3, 1, 2]$ 的中位数是 $2$，而数组 $[10, 1, 8, 3]$ 的中位数是 $3$。

保证数组中元素的绝对值互不相同。即，不存在一对下标 $1 \leq i < j \leq n$ 使得 $|a_i| = |a_j|$。

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$|a_i| \leq 10^6$，$|a_i| \neq |a_j|$）—— 数组 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，如果可以通过操作使得下标 $1$ 的元素成为数组的中位数，则输出 "YES"，否则输出 "NO"。

你可以以任意大小写输出答案（例如，"yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定回答）。

示例

输入

7
3
2 3 1
5
1 2 3 4 5
4
4 2 0 -5
4
-5 0 4 3
4
-10 8 3 2
1
1
10
9 1000 -999 -13 456 -223 23 24 10 0

输出

YES
YES
YES
NO
NO
YES
YES

说明

• 第一个测试用例：$a_1 = 2$ 已经是数组 $a = [2, 3, 1]$ 的中位数，因此不需要进行操作。

• 第二个测试用例：我们可以进行两次操作：一次在下标 $2$，一次在下标 $5$。数组变为 $[1, -2, 3, 4, -5]$，其中位数为 $1$。

• 第三个测试用例：如果对下标 $1$ 进行操作，数组将变为 $[-4, 2, 0, -5]$，其中位数为 $-4$。

• 第四个测试用例：可以证明，无论进行多少次操作，都无法使数组的中位数变为 $5$ 或 $-5$。

• 第五个测试用例：可以证明，无法使中位数变为 $a_1 = -10$ 或其相反数 $10$。

• 第六个测试用例：$n = 1$ 时，唯一的元素就是中位数，因此答案是 "YES"。

• 第七个测试用例：存在一种操作方案使得 $a_1 = 9$ 成为中位数。