← 返回题目列表

Codeforces · 2102/B

B. 挑剔的猫

中文机器翻译题面 查看原题

给定一个整数数组 $$$a_1, a_2, \ldots, a_n$$$。您可以执行以下操作任意次数(可能为零):

  • 选择索引 $$$i$$$ ($$$1\le i\le n$$$)。将 $$$a_i$$$ 乘以 $$$-1$$$ (即更新 $$$a_i := -a_i$$$)。

你的任务是确定在进行任意多次上述操作后是否可以使索引 $$$1$$$ 处的元素成为数组的中位数。请注意,操作也可以应用于索引 $$$1$$$,这意味着中位数可以是 $$$a_1$$$ 的原始值或其负值。

数组 $$$b_1, b_2, \ldots, b_m$$$ 的中位数定义为 $$$\left\lceil \frac{m}{2} \right\rceil$$$-th$$$^{\text{*}}$$$ 数组 $$$b$$$ 的最小元素。例如,数组 $$$[3, 1, 2]$$$ 的中位数是 $$$2$$$,而数组 $$$[10, 1, 8, 3]$$$ 的中位数是 $$$3$$$。

保证$$$a$$$ 的元素的绝对值不同。形式上,不存在索引对 $$$1\le i \lt j\le n$$$,其中 $$$|a_i| = |a_j|$$$。

$$$^{\text{*}}$$$$$$\lceil x \rceil$$$ 是上限函数,返回大于或等于 $$$x$$$ 的最小整数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

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

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

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

输出

对于每个测试用例,输出“是"如果可以使索引$$$1$$$处的元素成为数组的中位数,并且"NO”否则。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。

示例

输入
复制

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$$$。