We have an array of length $n$. Initially, each element is equal to $0$ and there is a pointer located on the first element.

We can do the following two kinds of operations any number of times (possibly zero) in any order:

If the pointer is not on the last element, increase the element the pointer is currently on by $1$. Then move it to the next element.

If the pointer is not on the first element, decrease the element the pointer is currently on by $1$. Then move it to the previous element.

But there is one additional rule. After we are done, the pointer has to be on the first element.

You are given an array $a$. Determine whether it's possible to obtain $a$ after some operations or not.


-----Input-----

The first line contains a single integer $t$ $(1\le t\le 1000)$  — the number of test cases. The description of the test cases follows.

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

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

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


-----Output-----

For each test case, print "Yes" (without quotes) if it's possible to obtain $a$ after some operations, and "No" (without quotes) otherwise.

You can output "Yes" and "No" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).


-----Examples-----

Input
7
2
1 0
4
2 -1 -1 0
4
1 -4 3 0
4
1 -1 1 -1
5
1 2 3 4 -10
7
2 -1 1 -2 0 0 0
1
0
Output
No
Yes
No
No
Yes
Yes
Yes


-----Note-----

In the first test case we can obtain the array after some operations, but the pointer won't be on the first element.

One way of obtaining the array in the second test case is shown below.

$\langle \underline{0}, 0, 0, 0\rangle \to \langle 1, \underline{0}, 0, 0 \rangle \to \langle \underline{1}, -1, 0, 0\rangle \to \langle 2, \underline{-1}, 0, 0\rangle \to \langle 2, 0, \underline{0}, 0\rangle \to \langle 2, \underline{0}, -1, 0\rangle \to \langle \underline{2}, -1, -1, 0\rangle$

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
def ss(l):
	n = len(l)
	if sum(l) != 0:
		return 'No'
	t = 0
	li = n - 1
	while li >= 0 and l[li] == 0:
		li -= 1
	for i in range(n):
		t += l[i]
		if t <= 0 and i < li:
			return 'No'
	return 'Yes'
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(ss(l))


import math as m
i = input()
inp = []
for a in range(int(i)):
	input()
	inp.append([int(x) for x in input().split()])

def logic(arr):
	n = len(arr)
	j = n - 1
	while j >= 0 and arr[j] == 0:
		j -= 1
	arr = arr[:j + 1]
	if arr == []:
		return 'Yes'
	elif arr[0] < 1:
		return 'No'
	s = 0
	n = len(arr)
	for i in range(n):
		s += arr[i]
		if s <= 0 and i != n - 1:
			return 'No'
	if s == 0:
		return 'Yes'
	else:
		return 'No'
for arr in inp:
	print(logic(arr))


def dirinc(N, array):
	if array[0] < 0 or array[-1] > 0 or sum(array) != 0:
		print('No')
		return
	runsum = 0
	for i in range(N):
		runsum = runsum + array[i]
		if runsum < 0:
			print('No')
			return
		if runsum == 0:
			j = i + 1
			while j < N:
				if array[j] != 0:
					print('No')
					return
				j = j + 1
			break
	print('Yes')
M = int(input())
for i in range(M):
	N = int(input())
	array = list(map(int, input().split()))
	dirinc(N, array)


def directional(arr, n):
	sum = 0
	yes = True
	for i in range(n):
		sum += arr[i]
		if sum < 0:
			yes = False
			break
		if sum == 0:
			for j in range(i + 1, n):
				if arr[j] != 0:
					yes = False
					break
			break
	if sum == 0 and yes:
		print('Yes')
	else:
		print('No')
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	directional(arr, n)


def check_r(n, l):
	s = 0
	for i in range(n):
		s += l[i]
		if s < 0:
			return 'No'
		if s == 0 and i != n - 1:
			if l[i + 1] != 0:
				return 'No'
	if s == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	print(check_r(n, l))


def meow(n, l):
	i = n - 1
	sumo = 0
	while i >= 0:
		if l[i] == 0:
			l.pop()
		elif l[i] < 0:
			if i == 0:
				return 'No'
				break
			else:
				break
		else:
			return 'No'
			break
		i = i - 1
	if len(l) == 0:
		return 'Yes'
	elif i != 0:
		while i >= 0:
			sumo = sumo + l[i]
			if i != 0:
				if sumo > -1:
					return 'No'
					break
				else:
					pass
			elif sumo == 0:
				return 'Yes'
				break
			else:
				return 'No'
				break
			i = i - 1
	else:
		return 'No'
tt = 0
t = int(input())
while tt < t:
	n = int(input())
	l = list(map(int, input().split()))
	print(meow(n, l))
	tt = tt + 1


def func():
	n = int(input())
	arr = list(map(int, input().split()))
	sm = sum(arr)
	if sm != 0 or arr[0] < 0 or arr[-1] > 0:
		print('No')
		return
	sm = arr[n - 1]
	for i in range(n - 2, 0, -1):
		if arr[i] != 0:
			sm += arr[i]
			if sm >= 0:
				print('No')
				return
	print('Yes')
tc = int(input())
while tc > 0:
	func()
	tc -= 1


from itertools import count

def isPossible(inp, n):
	sum = 0
	if inp[0] < 0:
		return False
	for i in inp:
		sum += i
	if sum != 0:
		return False
	if n <= 2:
		return True
	currSum = 0
	pre = []
	for i in inp:
		currSum += i
		pre.append(currSum)
	flag = 0
	for i in range(n - 1):
		if pre[i] < 0:
			return False
		elif pre[i] == 0:
			flag = 1
		elif flag:
			return False
	return True
t = int(input())
while t:
	t -= 1
	n = int(input())
	inp = list(map(int, input().split()))
	if isPossible(inp, n):
		print('Yes')
	else:
		print('No')


s = int(input())
for _ in range(s):
	n = int(input())
	b = list(map(int, input().split()))
	c = b[0]
	for i in range(1, n):
		if c < 0:
			break
		elif c == 0:
			if b[i] != 0:
				break
		else:
			c += b[i]
	else:
		if c == 0:
			print('Yes')
			continue
	print('No')


def solution():
	n = int(input())
	a = list(map(int, input().split()))
	if sum(a) != 0:
		print('No')
		return
	total = 0
	flag = True
	for i in reversed(a[1:]):
		if flag:
			if i == 0:
				continue
			else:
				flag = False
		total += i
		if total >= 0:
			print('No')
			return
	print('Yes')
try:
	import sys
	import os
	if os.path.exists('.cpl_files/3.in.txt'):
		sys.stdin = open('.cpl_files/3.in.txt', 'r')
		sys.stdout = open('.cpl_files/3.out.txt', 'w')
except:
	pass
t = int(input())
while t:
	solution()
	t -= 1


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	s = tag = 0
	for i in range(n):
		if a[i] and tag:
			return False
		s += a[i]
		if s < 0:
			return False
		tag = s == 0
	if s:
		return False
	return True
T = int(input())
for _ in range(T):
	if solve():
		print('Yes')
	else:
		print('No')


testcases = int(input())
for i in range(testcases):
	n = int(input())
	A = list(map(int, input().split()))
	sum = A[0]
	j = 1
	while sum > 0 and j < n:
		sum += A[j]
		j += 1
	if sum < 0:
		print('No')
	elif sum == 0:
		f = A[j:]
		b = True
		for k in f:
			if k != 0:
				b = False
		if b:
			print('Yes')
		else:
			print('No')
	elif j == n and sum != 0:
		print('No')


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	ind = -1
	res = 0
	if n == 1:
		if a == [0]:
			print('Yes')
		else:
			print('No')
		return
	for i in range(n):
		if a[i] < res:
			print('No')
			return
		res -= a[i]
		if res == 0:
			ind = i
			break
	if ind == -1:
		print('No')
		return
	for i in range(ind + 1, n):
		if a[i] != 0:
			print('No')
			return
	print('Yes')
t = int(input())
for i in range(t):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	q = 0
	for j in range(n - 1, 0, -1):
		if arr[j] != 0:
			ans += arr[j]
			if ans >= 0:
				q += 1
				break
	ans += arr[0]
	if ans == 0 and q == 0:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	i = n - 1
	while a[i] == 0 and i > 0:
		i -= 1
	l = 0
	ans = 'No'
	while i >= 0:
		l += a[i]
		if l >= 0:
			break
		i -= 1
	if i == 0 and l == 0:
		ans = 'Yes'
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input().split()
	for i in range(len(s) - 1, -1, -1):
		if s[i] != '0':
			break
		del s[i]
	a = list(map(int, s))[::-1]
	ok = True
	if a:
		if a[-1] <= 0:
			ok = False
		prefix = 0
		for i in range(len(a) - 1):
			prefix += a[i]
			if prefix >= 0:
				ok = False
		if prefix + a[-1] != 0:
			ok = False
	if ok:
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	tot = a[0]
	for i in range(1, n):
		if tot < 0:
			break
		elif tot == 0:
			if a[i] != 0:
				break
		else:
			tot += a[i]
	else:
		if tot == 0:
			print('Yes')
			continue
	print('No')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	while n > 0 and a[n - 1] == 0:
		n -= 1
	su = 0
	for i in range(0, n):
		su += a[i]
		if su < 0 or (su == 0 and i < n - 1):
			su = -1
			break
	print('Yes' if su == 0 else 'No')


MOD = 10 ** 9 + 7
fac_mem = [1]

def fac(n):
	while len(fac_mem) < n + 1:
		fac_mem.append(fac_mem[-1] * len(fac_mem) % MOD)
	return fac_mem[n]

def perm(n, k):
	return fac(n) * pow(fac(k), MOD - 2, MOD) % MOD

def comb(n, k):
	return fac(n) * pow(fac(k) * fac(n - k) % MOD, MOD - 2, MOD) % MOD
for case in range(int(input())):
	n = int(input())
	a = [int(j) for j in input().split()]
	s = a[0]
	possible = True
	for i in a[1:]:
		if s == 0 and i != 0 or s < 0:
			possible = False
		s += i
	print(['No', 'Yes'][possible and s == 0])


for _ in range(int(input())):
	n = int(input())
	if False:
		print('Tanmay')
	a = [int(x) for x in input().split()]
	if sum(a) != 0 or a[0] < 0 or a[-1] > 0:
		print('No')
		continue
	i = n - 1
	while i > 0 and a[i] == 0:
		i -= 1
	s = 0
	f = True
	while i > 0:
		s += a[i]
		if s >= 0:
			print('No')
			f = False
			break
		i -= 1
	if f:
		print('Yes')


def ispossible(arr, n):
	i = 0
	if n == 1:
		if arr[i] == 0:
			return True
		else:
			return False
	else:
		taken = 0
		i = 0
		j = n - 1
		random_arr = [0] * n
		while j >= 0 and arr[j] == random_arr[j]:
			random_arr[j] = 1
			j -= 1
		while i < n:
			if i == n - 1:
				taken = taken + arr[i]
				if taken == 0:
					return True
				else:
					return False
			else:
				taken = taken + arr[i]
				if taken == 0:
					if random_arr[i + 1] == 1:
						return True
					else:
						return False
				elif taken < 0:
					return False
				i += 1
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if ispossible(arr, n) == True:
		print('Yes')
	else:
		print('No')


strng = lambda : input()
inp = lambda : int(input())
mul = lambda : map(int, input().split())
jn = lambda x, l: x.join(map(str, l))
strlst = lambda : list(input())
lst = lambda : list(map(int, input().split()))
dd = lambda : defaultdict(lambda : 0)
import sys
input = sys.stdin.readline
from collections import defaultdict
from math import ceil, log, floor, sqrt, gcd, log10
for _ in range(inp()):
	n = inp()
	a = lst()
	s = 0
	flag = False
	for i in range(n - 1, -1, -1):
		s += a[i]
		if s >= 0 and a[i] != 0 and (i != 0):
			flag = True
			break
	if flag:
		print('No')
		continue
	if s == 0:
		print('Yes')
		continue
	print('No')


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
t = int(input())
for _ in range(t):
	n = int(input())
	arr = get_list()

	def solve():
		if sum(arr) != 0:
			return False
		j = n - 1
		while j > -1 and arr[j] == 0:
			j -= 1
		s = 0
		for i in range(j + 1):
			s += arr[i]
			if s < 0:
				return False
			if s == 0 and i != j:
				return False
		return True
	if solve():
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if arr[0] == 0 and n == 1:
		print('Yes')
		continue
	if arr[0] < 0:
		print('No')
		continue
	cs = 0
	flag = True
	noted = -1
	for i in range(n):
		cs += arr[i]
		if cs < 0:
			print('No')
			flag = False
			break
		if cs == 0:
			noted = i
			break
	if flag:
		if noted == -1:
			print('No')
		elif noted == n - 1:
			print('Yes')
		else:
			flagt = True
			for i in range(noted + 1, n):
				if arr[i] != 0:
					flagt = False
					print('No')
					break
			if flagt:
				print('Yes')


for i in range(int(input())):
	n = int(input())
	a = []
	a = list(map(int, input().split()))
	can = 1
	if a[0] == 0:
		if a == [0] * n:
			print('Yes')
		else:
			print('No')
	else:
		sum = 0
		reached_zero = 0
		for j in range(n):
			sum += a[j]
			if sum < 0:
				can = 0
			if sum == 0:
				reached_zero = 1
			if reached_zero and sum != 0:
				can = 0
		if sum:
			can = 0
		print('Yes' if can else 'No')


for _ in [0] * int(input()):
	n = int(input())
	s = [*map(int, input().split())]
	index = -1
	m = 0
	for i in range(n):
		m += s[i]
		if m < 0:
			break
		if m == 0:
			index = i + 1
			break
	if index == -1:
		print('No')
		continue
	if index == n or (len(set(s[index:])) == 1 and s[index] == 0):
		print('Yes')
		continue
	print('No')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	sumArr = 0
	ans = 'Yes'
	sumFoundZero = False
	for i in range(n):
		sumArr += arr[i]
		if sumFoundZero and arr[i] != 0:
			ans == 'No'
			break
		if sumArr < 0:
			ans = 'No'
			break
		elif sumArr == 0:
			sumFoundZero = True
	if sumArr != 0:
		ans = 'No'
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().strip().split()))[:n]
	s = 0
	flag = True
	flag2 = True
	flag3 = True
	for ind in range(n):
		s += arr[ind]
		if s < 0:
			flag = False
			break
		elif s == 0:
			flag2 = False
		elif flag2 is False and s > 0:
			flag3 = False
		else:
			pass
	if sum(arr) != 0:
		print('No')
	elif n == 1 & arr[0] != 0:
		print('No')
	elif flag is False:
		print('No')
	elif flag3 is False:
		print('No')
	else:
		print('Yes')


k = int(input())
for _ in range(k):
	n = int(input())
	a = list(map(int, input().split()))
	b = a[0]
	for i in range(1, n):
		if b < 0:
			break
		elif b == 0:
			if a[i] != 0:
				break
		else:
			b += a[i]
	else:
		if b == 0:
			print('Yes')
			continue
	print('No')


num_tests = int(input())
for _ in range(num_tests):
	m = int(input())
	arr = list(map(int, input().split()))
	if sum(arr) != 0:
		print('No')
		continue
	sm = 0
	f = True
	for i in range(m):
		sm += arr[i]
		if sm < 0:
			print('No')
			f = False
			break
		if sm == 0:
			break
	if f:
		for j in range(m - 1, -1, -1):
			if arr[j] != 0:
				if j == i:
					print('Yes')
				else:
					print('No')
				break
		if i == 0 and j == 0:
			print('Yes')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	t = 0
	check = 0
	for i in range(n):
		t += a[i]
		if t < 0:
			check = 1
			break
		if t == 0 and i < n - 1:
			for j in range(i + 1, n):
				if a[j] != 0:
					check = 1
					break
			break
	if t != 0 and check == 0:
		check = 1
	if check == 1:
		print('No')
	else:
		print('Yes')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	while n > 0:
		if arr[n - 1] == 0:
			del arr[n - 1]
			n -= 1
		else:
			break
	if n == 0:
		print('Yes')
	else:
		cs = 0
		flag = True
		for i in range(n):
			cs += arr[i]
			if cs < 0:
				flag = False
			elif cs == 0 and i != n - 1:
				flag = False
		if cs != 0 or flag == False:
			print('No')
		else:
			print('Yes')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if sum(a) != 0:
		print('No')
	else:
		flag = 0
		sum1 = 0
		impossible = 0
		for i in range(n - 1, 0, -1):
			if flag == 0:
				if a[i] != 0:
					flag = 1
					sum1 = a[i]
					if sum1 > 0:
						impossible = 1
						break
			else:
				sum1 += a[i]
				if sum1 >= 0:
					impossible = 1
					break
		if impossible == 1:
			print('No')
		else:
			print('Yes')


T = int(input())
for x in range(T):
	n = int(input())
	A = [int(d) for d in input().split()]
	if sum(A) != 0:
		print('No')
		continue
	if A[-1] > 0 or A[0] < 0:
		print('No')
		continue
	end = n - 1
	while A[end] == 0 and end > 0:
		end -= 1
	running = 0
	good = True
	for a in range(n):
		running += A[a]
		if running < 0:
			good = False
			break
		if running == 0:
			if a != end:
				good = False
			break
	if good:
		print('Yes')
	else:
		print('No')