D. Максимум не меньше суммы
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ из $$$n$$$ целых чисел. Вам нужно проверить, верно ли, что неравенство $$$$$$\max(a_i, a_{i + 1}, \ldots, a_{j - 1}, a_{j}) \geq a_i + a_{i + 1} + \dots + a_{j - 1} + a_{j}$$$$$$ выполняется для всех пар индексов $$$(i, j)$$$, где $$$1 \leq i \leq j \leq n$$$.

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

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Первая строка каждого набора входных данныхх содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)  — размер массива.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

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

В примерах $$$1$$$ и $$$2$$$ данное неравенство выполняется для всех пар $$$(i, j)$$$.

В примере $$$3$$$ неравенство не выполняется для пары $$$(1, 2)$$$, так как $$$\max(2, 3) < 2 + 3$$$.