You are given an array $a$ of $n$ positive integers.

You can use the following operation as many times as you like: select any integer $1 \le k \le n$ and do one of two things:   decrement by one $k$ of the first elements of the array.  decrement by one $k$ of the last elements of the array. 

For example, if $n=5$ and $a=[3,2,2,1,4]$, then you can apply one of the following operations to it (not all possible options are listed below):   decrement from the first two elements of the array. After this operation $a=[2, 1, 2, 1, 4]$;  decrement from the last three elements of the array. After this operation $a=[3, 2, 1, 0, 3]$;  decrement from the first five elements of the array. After this operation $a=[2, 1, 1, 0, 3]$; 

Determine if it is possible to make all the elements of the array equal to zero by applying a certain number of operations.


-----Input-----

The first line contains one positive integer $t$ ($1 \le t \le 30000$) — the number of test cases. Then $t$ test cases follow.

Each test case begins with a line containing one integer $n$ ($1 \le n \le 30000$) — the number of elements in the array.

The second line of each test case contains $n$ integers $a_1 \ldots a_n$ ($1 \le a_i \le 10^6$).

The sum of $n$ over all test cases does not exceed $30000$.


-----Output-----

For each test case, output on a separate line:   YES, if it is possible to make all elements of the array equal to zero by applying a certain number of operations.  NO, otherwise. 

The letters in the words YES and NO can be outputed in any case.


-----Example-----
Input
4
3
1 2 1
5
11 7 9 6 8
5
1 3 1 3 1
4
5 2 1 10

Output
YES
YES
NO
YES

Difficulty: competition

Starter code:

Solutions:
import sys

input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    a = list(map(int,input().split()))
    for i in range(n-1,0,-1):
        a[i] -= a[i-1]

    minus = 0
    for i in range(1,n):
        if a[i]<0:
            minus -= a[i]

    if a[0] - minus >=0:
        print("YES")
    else:
        print("NO")


import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    l = list(map(int, input().split()))
    curr = 0
    for i in range(n-1):
        diff = l[i+1] - l[i]
        l[i] -= curr
        if diff > 0:
            curr += diff
    l[n-1] -= curr

    if min(l) >= 0:
        print('YES')
    else:
        print('NO')


t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    b = [0] * (n - 1)
    for i in range(n - 1):
        b[i] = a[i + 1] - a[i]
    mi = 10000000
    c = [0] * (n + 1)
    for i in range(n - 1):
        if b[i] < 0:
            c[i + 1] += b[i]
            c[0] -= b[i]
        else:
            c[i + 1] += b[i]
            c[-1] -= b[i]
    for i in range(n):
        c[i + 1] += c[i]
    for i in range(n):
        if c[i] > a[i]:
            print('NO')
            break
    else:
        print('YES')


import sys
input = sys.stdin.readline
import random

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

    #n=6
    #A=[random.randint(1,10) for i in range(n)]
    #print(A)

    REST=[-1]*n
    MIN=1<<60
    RESTMAX=0

    for i in range(n):
        MIN=min(MIN,A[i])

        if A[i]-MIN<RESTMAX:
            MIN=max(0,A[i]-RESTMAX)
            REST[i]=A[i]-MIN
            RESTMAX=max(RESTMAX,REST[i])

        else:
            REST[i]=A[i]-MIN
            RESTMAX=max(RESTMAX,REST[i])


    for i in range(1,n):
        if REST[i-1]==0:
            continue
        if REST[i-1]>REST[i]:
            print("NO")
            break
    else:
        print("YES")

    #print(REST,MIN)

        
        
    


import sys
from sys import stdin

tt = int(stdin.readline())

for loop in range(tt):

    n = int(stdin.readline())
    a = list(map(int,stdin.readline().split()))

    r = a[0]
    l = 0

    for i in range(n):

        if r + l < a[i]:
            l = a[i] - r
        elif r + l > a[i]:
            r = a[i] - l

    if r >= 0:
        print ("YES")
    else:
        print ("NO")

import sys
readline = sys.stdin.readline

T = int(readline())
INF = 10**9+7
Ans = [None]*T
for qu in range(T):
    N = int(readline())
    A = list(map(int, readline().split()))
    
    res = INF
    rem = 0
    for i in range(N):
        res = max(0, min(res, A[i]-rem))
        A[i] -= res
        rem = A[i]
    Ans[qu] = 'YES' if all(a2 - a1 >= 0 for a1, a2 in zip(A, A[1:])) else 'NO'

print('\n'.join(map(str, Ans)))

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    alst = list(map(int, input().split()))
    up = alst[0]
    down = 0
    for a in alst[1:]:
        if (up + down) == a:
            continue
        elif (up + down) < a:
            down = a - up
        else:
            up = a - down
        if up < 0 or down < 0:
            print("NO")
            return
    print("YES")
        
    
    
for _ in range(int(input())):
    main()