CF1646B.Quality vs Quantity

$ \def\myred#1{\color{red}{\underline{\bf{#1}}}} \def\myblue#1{\color{blue}{\overline{\bf{#1}}}} $ $\def\RED{\myred{Red}} \def\BLUE{\myblue{Blue}}$

You are given a sequence of $n$ non-negative integers $a_1, a_2, \ldots, a_n$. Initially, all the elements of the sequence are unpainted. You can paint each number \RED or \BLUE (but not both), or leave it unpainted.

For a color $c$, $\text{Count}(c)$ is the number of elements in the sequence painted with that color and $\text{Sum}(c)$ is the sum of the elements in the sequence painted with that color.

For example, if the given sequence is $[2, 8, 6, 3, 1]$ and it is painted this way: [\myblue{2}, 8, \myred{6}, \myblue{3}, 1] (where $6$ is painted red, $2$ and $3$ are painted blue, $1$ and $8$ are unpainted) then \text{Sum}(\RED)=6, \text{Sum}(\BLUE)=2+3=5, \text{Count}(\RED)=1, and \text{Count}(\BLUE)=2.

Determine if it is possible to paint the sequence so that \text{Sum}(\RED) \gt \text{Sum}(\BLUE) and \text{Count}(\RED) \lt \text{Count}(\BLUE).

$ \def\myred#1{\color{red}{\underline{\bf{#1}}}} \def\myblue#1{\color{blue}{\overline{\bf{#1}}}} $ $\def\RED{\myred{Red}} \def\BLUE{\myblue{Blue}}$

给定一个由 $n$ 个非负整数组成的序列 $a_1, a_2, \ldots, a_n$。初始时，序列中所有元素均未被涂色。你可以将每个数涂成 \RED 或 \BLUE（但不能同时涂两种颜色），也可以保持其未涂色。

对于一种颜色 $c$，记 $\text{Count}(c)$ 为该颜色所涂元素的个数，$\text{Sum}(c)$ 为该颜色所涂元素的数值之和。

例如，若给定序列为 $[2, 8, 6, 3, 1]$，并按如下方式涂色：[\myblue{2}, 8, \myred{6}, \myblue{3}, 1]（即 $6$ 涂为红色，$2$ 和 $3$ 涂为蓝色，$1$ 和 $8$ 保持未涂色），则有 \text{Sum}(\RED)=6，\text{Sum}(\BLUE)=2+3=5，\text{Count}(\RED)=1，\text{Count}(\BLUE)=2。

请判断是否存在一种涂色方案，使得 \text{Sum}(\RED) \gt \text{Sum}(\BLUE) 且 \text{Count}(\RED) \lt \text{Count}(\BLUE)。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). Description of the test cases follows.

The first line of each test case contains an integer $n$ ($3\le n\le 2\cdot 10^5$) — the length of the given sequence.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0\le a_i\le 10^9$) — the given sequence.

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。随后是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$3\le n\le 2\cdot 10^5$）—— 给定序列的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0\le a_i\le 10^9$）—— 给定的序列。

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

For each test case, print YES if it is possible to paint the given sequence satisfying the above requirements, and NO 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).

对于每个测试用例，如果能够按照上述要求对给定序列进行染色，则输出 YES；否则输出 NO。

YES 和 NO 的大小写不限（例如，字符串 yEs、yes、Yes 和 YES 均被视为肯定回答）。

In the first test case, there is no possible way to paint the sequence. For example, if you paint the sequence this way: [\myblue{1},\myblue{2},\myred{3}] (where $3$ is painted red, $1$ and $2$ are painted blue) then \text{Count}(\RED)=1 \lt \text{Count}(\BLUE)=2, but \text{Sum}(\RED)=3 \ngtr \text{Sum}(\BLUE)=3. So, this is not a possible way to paint the sequence.

In the second test case, a possible way to paint the sequence is described in the statement. We can see that \text{Sum}(\RED)=6 \gt \text{Sum}(\BLUE)=5 and \text{Count}(\RED)=1 \lt \text{Count}(\BLUE)=2.

In the third test case, there is no possible way to paint the sequence. For example, if you paint the sequence this way: [\myred{3},\myred{5},\myblue{4}, \myblue{2}] (where $3$ and $5$ are painted red, $4$ and $2$ are painted blue) then \text{Sum}(\RED) = 8 \gt \text{Sum}(\BLUE) = 6 but \text{Count}(\RED) = 2 \nless \text{Count}(\BLUE) = 2. So, this is not a possible way to paint the sequence.

In the fourth test case, it can be proven that there is no possible way to paint the sequence satisfying sum and count constraints.

在第一个测试用例中，不存在对序列进行染色的可行方案。例如，若将序列染色为：[\myblue{1},\myblue{2},\myred{3}]（其中 $3$ 染成红色，$1$ 和 $2$ 染成蓝色），则 \text{Count}(\RED)=1 \lt \text{Count}(\BLUE)=2，但 \text{Sum}(\RED)=3 \ngtr \text{Sum}(\BLUE)=3。因此，这不是一种可行的染色方案。

在第二个测试用例中，题目陈述中已描述了一种可行的染色方案。我们可以看出 \text{Sum}(\RED)=6 \gt \text{Sum}(\BLUE)=5 且 \text{Count}(\RED)=1 \lt \text{Count}(\BLUE)=2。

在第三个测试用例中，不存在对序列进行染色的可行方案。例如，若将序列染色为：[\myred{3},\myred{5},\myblue{4}, \myblue{2}]（其中 $3$ 和 $5$ 染成红色，$4$ 和 $2$ 染成蓝色），则 \text{Sum}(\RED) = 8 \gt \text{Sum}(\BLUE) = 6，但 \text{Count}(\RED) = 2 \nless \text{Count}(\BLUE) = 2。因此，这不是一种可行的染色方案。

在第四个测试用例中，可以证明不存在满足和与数量约束的染色方案。