Quality vs Quantity
Contest: Codeforces Round 774 (Div. 2)
Difficulty rating: 800
Tags: brute force, constructive algorithms, greedy, sortings, two pointers

$$$ \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) > \text{Sum}(\BLUE)$$$ and $$$\text{Count}(\RED) < \text{Count}(\BLUE)$$$.

Input format:
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$$$.

Output format:
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).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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 < \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 > \text{Sum}(\BLUE)=5$$$ and $$$\text{Count}(\RED)=1 < \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 > \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.

Example input:
4
3
1 2 3
5
2 8 6 3 1
4
3 5 4 2
5
1000000000 1000000000 1000000000 1000000000 1000000000

Example output:
NO
YES
NO
NO

Editorial:
$$$ \def\myred#1{\color{red}{\underline{\bf{#1}}}} \def\myblue#1{\color{blue}{\overline{\bf{#1}}}} $$$ $$$\def\RED{\myred{Red}} \def\BLUE{\myblue{Blue}}$$$
Suppose $$$\text{Count}(\RED)=k$$$. If a solution exists, then there is one with $$$\text{Count}(\BLUE)=k+1$$$, because if there are more than $$$k+1$$$ numbers painted blue, we can remove some of them until we have exactly $$$k+1$$$ numbers, and the sum of these numbers will be smaller.
As we want $$$\text{Sum}(\RED) > \text{Sum}(\BLUE)$$$ to hold, the optimal way to paint the numbers is to paint the $$$k$$$ largest numbers red, and the $$$k+1$$$ smallest numbers blue.
So, to solve the problem it is enough to sort the sequence, iterate over the value of $$$k$$$ and for each of them compute the sum of the $$$k$$$ largest numbers, the sum of the $$$k+1$$$ smallest numbers and compare them. This can be done efficiently by computing the sum of every prefix and suffix of the sorted sequence in linear time. This way, we can make a constant number of operations for each $$$k$$$.
Intended complexity: $$$\mathcal{O}(n\:\text{log}\:n)$$$