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

Сегодня Яссер и Адель пошли в магазин за пирожными. На полке в магазине стоят $$$n$$$ типов пирожных, пронумерованные от $$$1$$$ до $$$n$$$. Количество пирожных каждого типа бесконечно. Определим вкус $$$i$$$-го пирожного некоторой величиной $$$a_i$$$, которая является целым числом. В магазине есть как вкусные пирожные, так и неприятные, поэтому данная величина может быть положительной, нулем или отрицательной.

Яссер, разумеется, хочет попробовать их все, поэтому он купит ровно по одному пирожному каждого типа.

Адель, с другой стороны, выберет некоторый отрезок $$$[l, r]$$$ $$$(1 \le l \le r \le n)$$$, который содержит не все пирожные (он не может выбрать $$$[l, r] = [1, n]$$$) и купит ровно по одному пирожному каждого из типов $$$l, l + 1, \dots, r$$$.

После этого они сравнят суммарный вкус купленных ими пирожных. Яссер будет счастлив, если суммарный вкус пирожных, которые он купил, строго больше, чем суммарный вкус пирожных, которые купил Адель вне зависимости от выбора Адель.

Например, пусть вкус пирожных будет $$$[7, 4, -1]$$$. Яссер купит все, суммарный вкус будет равен $$$7 + 4 - 1 = 10$$$. Адель может выбрать отрезки $$$[7], [4], [-1], [7, 4]$$$ или $$$[4, -1]$$$, суммарный вкус будет равен $$$7, 4, -1, 11$$$ и $$$3$$$, соответственно. Адель может выбрать отрезок с суммарным вкусом $$$11$$$, и раз $$$10$$$ не строго больше $$$11$$$, то Яссер не будет счастлив :(

Узнайте, будет ли Яссер счастлив после похода в магазин.

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

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

В первой строке каждого набора входных данных записано одно целое число $$$n$$$ ($$$2 \le n \le 10^5$$$).

Во второй строке каждого набора входных данных записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$), где $$$a_i$$$ является вкусом $$$i$$$-го типа пирожного.

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

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

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

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

В первом примере суммарный вкус любого отрезка, который может выбрать Адель, меньше, чем суммарный вкус всех пирожных.

Во втором примере Адель выберет отрезок $$$[1, 2]$$$ с суммарным вкусом $$$11$$$, что не меньше, чем суммарный вкус всех пирожных, который равен $$$10$$$.

В третьем примере, Адель может выбрать отрезок $$$[3, 3]$$$ c суммарным вкусом $$$5$$$. Обратите внимание, что вкус пирожных у Яссера тоже равен $$$5$$$, поэтому в данном случае суммарный вкус пирожных, которые купил Яссер, не строго больше, чем суммарный вкус пирожных, которые купил Адель.