You are given an array $a$ of $n$ integers. You are asked to find out if the inequality $$\max(a_i, a_{i + 1}, \ldots, a_{j - 1}, a_{j}) \geq a_i + a_{i + 1} + \dots + a_{j - 1} + a_{j}$$ holds for all pairs of indices $(i, j)$, where $1 \leq i \leq j \leq n$.


-----Input-----

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

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$)  — the size of the array.

The next line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, on a new line output "YES" if the condition is satisfied for the given array, and "NO" otherwise. You can print each letter in any case (upper or lower).


-----Examples-----

Input
3
4
-1 1 -1 2
5
-1 2 -3 2 -1
3
2 3 -1
Output
YES
YES
NO


-----Note-----

In test cases $1$ and $2$, the given condition is satisfied for all $(i, j)$ pairs.

In test case $3$, the condition isn't satisfied for the pair $(1, 2)$ as $\max(2, 3) < 2 + 3$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Sorting

Amortized analysis

Implementation

Divide and conquer

Data structures


Solutions:
import sys
input = sys.stdin.readline

def sol(arr, n):
	l = 0
	r = n - 1
	for i in range(n - 1):
		if arr[i] > 0 and arr[i + 1] > 0:
			return 'NO'
	while l < n and arr[l] <= 0:
		l += 1
	while r >= 0 and arr[r] <= 0:
		r -= 1
	if r < 0:
		return 'YES'
	res = []
	while l <= r:
		acc = 0
		if arr[l] <= 0:
			while l <= r and arr[l] <= 0:
				acc += arr[l]
				l += 1
		else:
			acc = arr[l]
			l += 1
		res.append(acc)
	if len(res) <= 2:
		return 'YES'
	stack = [0]
	dp = [0] * len(res)
	for i in range(2, len(res), 2):
		acc = res[i - 1]
		while stack and res[stack[-1]] <= res[i]:
			acc += res[stack[-1]]
			if acc > 0:
				return 'NO'
			acc += dp[stack.pop()]
		dp[i] = acc
		stack.append(i)
	stack = [len(res) - 1]
	dp = [0] * len(res)
	for i in range(len(res) - 3, -1, -2):
		acc = res[i + 1]
		while stack and res[stack[-1]] <= res[i]:
			acc += res[stack[-1]]
			if acc > 0:
				return 'NO'
			acc += dp[stack.pop()]
		dp[i] = acc
		stack.append(i)
	return 'YES'
t = int(input())
for case in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(sol(arr, n))


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	(ng1, ng2) = ([-1] * n, [-1] * n)
	(st1, st2) = ([], [])
	(ps, ss) = ([0] * n, [0] * n)
	v1 = v2 = 0
	for i in range(n):
		while st1 and arr[st1[-1]] <= arr[i]:
			ng1[st1.pop()] = i
		st1.append(i)
		v1 += arr[i]
		ps[i] = v1
		j = n - 1 - i
		while st2 and arr[st2[-1]] <= arr[j]:
			ng2[st2.pop()] = j
		st2.append(j)
		v2 += arr[j]
		ss[j] = v2
	for i in range(n):
		if arr[i] <= 0:
			continue
		if ng1[i] > -1:
			if ng1[i] == i + 1:
				return 'NO'
			v = ps[ng1[i] - 1] - ps[i]
			if abs(v) < arr[i]:
				return 'NO'
		elif i != n - 1:
			v = ps[-1] - ps[i]
			if v > 0:
				return 'NO'
		if ng2[i] > -1:
			if ng2[i] == i - 1:
				return 'NO'
			v = ss[ng2[i] + 1] - ss[i]
			if abs(v) < arr[i]:
				return 'NO'
		elif i != 0:
			v = ss[0] - ss[i]
			if v > 0:
				return 'NO'
	return 'YES'
t = int(input())
for i in range(t):
	print(solve())


import itertools
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = [10 ** 10] + [*map(int, input().split())]
	p = list(itertools.accumulate(a))
	stk = [0]
	minP1 = [0] * (n + 1)
	minP = [2 * a[0]]
	res = 'YES'
	for i in range(1, n + 1):
		minP1[i] = p[i - 1]
		while a[stk[-1]] <= a[i]:
			minP1[i] = min(minP1[i], minP1[stk[-1]])
			minP.pop()
			stk.pop()
		stk.append(i)
		minP.append(min(minP[-1], a[i] + minP1[i]))
		if p[i] - minP[-1] > 0:
			res = 'NO'
			break
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	pre = [0]
	suf = [0]
	min_suf = [0] * n
	min_pre = [0] * n
	stk = []
	flag = True
	for i in range(n):
		pre.append(pre[-1] + a[i])
		temp_min = pre[i]
		while len(stk) and a[stk[-1]] <= a[i]:
			temp_min = min(temp_min, min_pre[stk[-1]])
			stk.pop()
		min_pre[i] = temp_min
		stk.append(i)
	stk.clear()
	for i in range(n - 1, -1, -1):
		suf.append(suf[-1] + a[i])
		temp_min = suf[n - 1 - i]
		while len(stk) and a[stk[-1]] <= a[i]:
			temp_min = min(temp_min, min_suf[stk[-1]])
			stk.pop()
		min_suf[i] = temp_min
		stk.append(i)
	for i in range(n):
		if suf[n - i] - min_suf[i] + pre[i + 1] - min_pre[i] - 2 * a[i] > 0:
			print('NO')
			flag = False
			break
	if flag:
		print('YES')