B. Качество против количества
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

$$$ \def\myred#1{\color{red}{\underline{\bf{#1}}}} \def\myblue#1{\color{blue}{\overline{\bf{#1}}}} $$$ $$$\def\RED{\myred{\unicode{1050}\unicode{1088}\unicode{1072}\unicode{1089}\unicode{1085}\unicode{1099}\unicode{1081}}} \def\BLUE{\myblue{\unicode{1057}\unicode{1080}\unicode{1085}\unicode{1080}\unicode{1081}}}$$$

Вам дана последовательность из $$$n$$$ неотрицательных целых чисел $$$a_1, a_2, \ldots, a_n$$$. Изначально все элементы непокрашены. Вы можете покрасить каждое число в $$$\RED$$$ или $$$\BLUE$$$ (но не в оба) или оставить его непокрашенным.

Обозначим за $$$\text{Count}(c)$$$ количество элементов последовательности, покрашенных в $$$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) > \text{Sum}(\BLUE)$$$ и $$$\text{Count}(\RED) < \text{Count}(\BLUE)$$$.

Входные данные

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите YES, если возможно раскрасить данную последовательность, удовлетворив заданные ограничения, и NO в противном случае.

Вы можете выводить YES и NO в любом регистре (например, строки yEs, yes, Yes и YES будут считаться положительным ответом).

Пример
Входные данные
4
3
1 2 3
5
2 8 6 3 1
4
3 5 4 2
5
1000000000 1000000000 1000000000 1000000000 1000000000
Выходные данные
NO
YES
NO
NO
Примечание

В первом примере нет способа раскрасить элементы заданным образом. Например, если раскрасить последовательность следующим образом: $$$[\myblue{1},\myblue{2},\myred{3}]$$$ (где $$$3$$$ покрашена красным, $$$1$$$ и $$$2$$$ покрашены синим), то $$$\text{Count}(\RED)=1 < \text{Count}(\BLUE)=2$$$, но $$$\text{Sum}(\RED)=3 \ngtr \text{Sum}(\BLUE)=3$$$. Поэтому это не является корректным способом раскрасить последовательность.

Во втором примере один из возможных способов раскрасить последовательность показан в условии. Легко видеть, что $$$\text{Sum}(\RED)=6 > \text{Sum}(\BLUE)=5$$$, а также $$$\text{Count}(\RED)=1 < \text{Count}(\BLUE)=2$$$.

В третьем примере можно показать, что нет способа раскрасить последовательность правильным образом. Например, если раскрасить последовательность следующим образом: $$$[\myred{3},\myred{5},\myblue{4}, \myblue{2}]$$$ (где $$$3$$$ и $$$5$$$ покрашены красным, $$$4$$$ и $$$2$$$ покрашены синим), то $$$\text{Sum}(\RED) = 8 > \text{Sum}(\BLUE) = 6$$$, но $$$\text{Count}(\RED) = 2 \nless \text{Count}(\BLUE) = 2$$$. Поэтому это не является корректным способом раскрасить последовательность.

В четвертом примере можно показать, что нет способа раскрасить последовательность правильным образом.