Today, Yasser and Adel are at the shop buying cupcakes. There are $n$ cupcake types, arranged from $1$ to $n$ on the shelf, and there are infinitely many of each type. The tastiness of a cupcake of type $i$ is an integer $a_i$. There are both tasty and nasty cupcakes, so the tastiness can be positive, zero or negative.

Yasser, of course, wants to try them all, so he will buy exactly one cupcake of each type.

On the other hand, Adel will choose some segment $[l, r]$ $(1 \le l \le r \le n)$ that does not include all of cupcakes (he can't choose $[l, r] = [1, n]$) and buy exactly one cupcake of each of types $l, l + 1, \dots, r$.

After that they will compare the total tastiness of the cupcakes each of them have bought. Yasser will be happy if the total tastiness of cupcakes he buys is strictly greater than the total tastiness of cupcakes Adel buys regardless of Adel's choice.

For example, let the tastinesses of the cupcakes be $[7, 4, -1]$. Yasser will buy all of them, the total tastiness will be $7 + 4 - 1 = 10$. Adel can choose segments $[7], [4], [-1], [7, 4]$ or $[4, -1]$, their total tastinesses are $7, 4, -1, 11$ and $3$, respectively. Adel can choose segment with tastiness $11$, and as $10$ is not strictly greater than $11$, Yasser won't be happy :(

Find out if Yasser will be happy after visiting the shop.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains $n$ ($2 \le n \le 10^5$).

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$), where $a_i$ represents the tastiness of the $i$-th type of cupcake.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$.


-----Output-----

For each test case, print "YES", if the total tastiness of cupcakes Yasser buys will always be strictly greater than the total tastiness of cupcakes Adel buys regardless of Adel's choice. Otherwise, print "NO".


-----Example-----
Input
3
4
1 2 3 4
3
7 4 -1
3
5 -5 5

Output
YES
NO
NO



-----Note-----

In the first example, the total tastiness of any segment Adel can choose is less than the total tastiness of all cupcakes.

In the second example, Adel will choose the segment $[1, 2]$ with total tastiness $11$, which is not less than the total tastiness of all cupcakes, which is $10$.

In the third example, Adel can choose the segment $[3, 3]$ with total tastiness of $5$. Note that Yasser's cupcakes' total tastiness is also $5$, so in that case, the total tastiness of Yasser's cupcakes isn't strictly greater than the total tastiness of Adel's cupcakes.

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    input()
    l = list(map(int,input().split()))

    bad = False
    
    curr = 0
    for v in l:
        curr += v
        if curr <= 0:
            bad = True
            break

    l.reverse()
    curr = 0
    for v in l:
        curr += v
        if curr <= 0:
            bad = True
            break

    if bad:
        print('NO')
    else:
        print('YES')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int,input().split()))
	ans = "YES"
	cur = 0
	for i in range(n-1):
		cur += a[i]
		if cur <= 0:
			ans = "NO"
	cur = 0	
	for i in range(n-1,0,-1):
		cur += a[i]
		if cur <= 0:
			ans = "NO"
	print(ans)			


import sys
input=sys.stdin.readline
t=int(input())
for _ in range(t):
    n=int(input())
    it=list(map(int,input().split()))
    su=0
    ma=-float("inf")
    for i in range(n-1):
        su+=it[i]
        ma=max(ma,su)
        su=max(su,0)
    su=0
    for i in range(1,n):
        su+=it[i]
        ma=max(ma,su)
        su=max(su,0)
    if sum(it)>ma:
        print("YES")
    else:
        print("NO")


q = int(input())
for re in range(q):
	n = int(input())
	l = list(map(int,input().split()))
	pref = [0] * n
	pref[0] = l[0]
	for i in range(1, n):
		pref[i] = pref[i-1] + l[i]
	prefr = [0] * n
	prefr[0] = l[n-1]
	for i in range(1,n):
		prefr[i] = prefr[i-1] + l[n-i-1]
	odp = 1
	for i in range(n):
		if prefr[i] <= 0:
			odp = 0
			break
	for i in range(n):
		if pref[i] <=0:
			odp = 0
			break
	if odp:
		print("YES")
	else:
		print("NO")

# = map(int, input().split())
# = list(map(int, input().split()))
t = int(input())
for _ in range(t):
    n = int(input())
    z = list(map(int, input().split()))
    sm = sum(z)
    maxsum = 0
    minpref = 0
    curpref = 0
    for a in z[:-1]:
        curpref += a
        if curpref - minpref > maxsum:
            maxsum = curpref - minpref
        minpref = min(minpref, curpref)
    minpref = 0
    curpref = 0
    for a in z[1:]:
        curpref += a
        if curpref - minpref > maxsum:
            maxsum = curpref - minpref
        minpref = min(minpref, curpref)
    if maxsum < sm:
        print('YES')
    else:
        print('NO')


def maxSubArraySum(a,size): 
    max_so_far =a[0] 
    curr_max = a[0] 
      
    for i in range(1,size): 
        curr_max = max(a[i], curr_max + a[i]) 
        max_so_far = max(max_so_far,curr_max) 
          
    return max_so_far 

def main():
    t = int(input())
    ans = []
    for i in range(t):
        n = int(input())
        arr = list(map(int,input().split()))
        total = sum(arr)
        sum1 = maxSubArraySum(arr[:n-1],n-1)
        sum2 = maxSubArraySum(arr[1:],n-1)
        if total > max(sum1,sum2):
            ans.append('YES')
        else:
            ans.append('NO')

    for i in ans:
        print(i)


main()


def mi():
        return list(map(int, input().split()))
'''
3
4
1 2 3 4
3
7 4 -1
3
5 -5 5
'''


def maxSubArraySum(a, size):
    max_so_far = a[0]
    curr_max = a[0]

    for i in range(1, size):
        curr_max = max(a[i], curr_max + a[i])
        max_so_far = max(max_so_far, curr_max)

    return max_so_far

for _ in range(int(input())):
        n = int(input())
        a = list(mi())
        ade = max(maxSubArraySum(a,n-1), maxSubArraySum(a[1:],n-1))
        if sum(a)>ade:
                print ('YES')
        else:
                print ('NO')


test = int(input())
for z in range(test):
    amount = int(input())
    numb = list(map(int, input().split()))
    all = sum(numb)
    happy = True
    summ = 0
    for i in range(amount - 1):
        summ += numb[i]
        if summ <= 0:
            happy = False
            break
    if (not happy):
        print('NO')
        continue
    else:
        summ = 0
        for i in range(amount - 1, 0, -1):
            summ += numb[i]
            if summ <= 0:
                happy = False
                break
        if not happy:
            print('NO')
            continue
    print("YES")

import sys
input = sys.stdin.readline

from itertools import accumulate

t=int(input())

for test in range(t):
    n=int(input())
    A=list(map(int,input().split()))

    S=list(accumulate(A))

    for s in S:
        if s<=0:
            print("NO")
            break

    else:
        B=A[::-1]

        S=list(accumulate(B))

        for s in S:
            if s<=0:
                print("NO")
                break

        else:
            print("YES")
        



import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    yasser = sum(a)
    ans = True
    cur = 0
    for i in range(n-1):
        cur += a[i]
        if cur <= 0:
            ans = False
            break
    cur = 0
    for i in reversed(list(range(1, n))):
        cur += a[i]
        if cur <= 0:
            ans = False
            break
    if ans:
        print("YES")
    else:
        print("NO")

t = int(input())
for i in range(t):
    solve()



def maxSubArraySum(a,size): 
      
    max_so_far = 0
    max_ending_here = 0
      
    for i in range(0, size): 
        max_ending_here = max_ending_here + a[i] 
        if max_ending_here < 0: 
            max_ending_here = 0
          
        # Do not compare for all elements. Compare only    
        # when  max_ending_here > 0 
        elif (max_so_far < max_ending_here): 
            max_so_far = max_ending_here 
              
    return max_so_far
def case():
    n = int(input())
    a = list(map(int, input().split()))
    ans1 = maxSubArraySum(a[1:], n-1)
    ans2 = maxSubArraySum(a[:-1], n-1)
    s = sum(a)
    if s > max(ans1, ans2):
        print("YES")
    else:
        print("NO")
for _ in range(int(input())):
    case()

def ans(arr, n):
    left = arr[0]
    if left <= 0:
        return False
    for i in range (1, n):
        left += arr[i]
        if left <= 0:
            return False
    right = arr[n - 1]
    if right <= 0:
        return False
    i = n - 2
    while i >= 0:
        right += arr[i]
        if right <= 0:
            return False
        i -= 1
    return True
t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(map(int,input().split()))
    if ans(arr, n):
        print("YES")
    else:
        print("NO")

def max_subarray(arr):
    max_ending = max_current = arr[0]

    for i in arr[1:]:
        max_ending = max(i, max_ending + i)
        max_current = max(max_current, max_ending)
    return max_current

t = int(input())

for _ in range(t):
    n = int(input())
    arr = list(map(int, input().split()))
    yas = sum(arr)
    adel = max(max_subarray(arr[1:]), max_subarray(arr[:n-1]))
    if yas>adel:
        print("YES")
    else:
        print("NO")

def maxCrossingSum(arr, l, m, h):
    sm = 0
    left_sum = -10000

    for i in range(m, l - 1, -1):
        sm = sm + arr[i]

        if (sm > left_sum):
            left_sum = sm
    sm = 0
    right_sum = -1000
    for i in range(m + 1, h + 1):
        sm = sm + arr[i]

        if (sm > right_sum):
            right_sum = sm

    return left_sum + right_sum

def maxSubArraySum(arr, l, h):
    if (l == h):
        return arr[l]
    m = (l+h)//2
    return max(maxSubArraySum(arr, l, m),
               maxSubArraySum(arr, m + 1, h),
               maxCrossingSum(arr, l, m, h))


for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    y = sum(a)
    s1, s2 = maxSubArraySum(a, 0, n-2), maxSubArraySum(a, 1, n-1)
    #print(s1, s2, y)
    if s1 >= y or s2 >= y:
        print("NO")
    else:
        print('YES')


def ma(a,size): 
       
    max_so_far = - 10**9
    max_ending_here = 0
       
    for i in range(0, size): 
        max_ending_here = max_ending_here + a[i] 
        if (max_so_far < max_ending_here): 
            max_so_far = max_ending_here 
  
        if max_ending_here < 0: 
            max_ending_here = 0   
    return max_so_far
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    k=ma(a[1:],len(a)-1)
    j=ma(a[:n-1],len(a)-1)
    if sum(a)>max(j,k):
        print('YES')
    else:
        print('NO')