There are N tasks waiting in line to be executed. The execution time for the i^{th} task is A_{i} seconds. 

Chef has two processors to execute these N tasks. Both these processors work simultaneously. Each processor executes the assigned tasks one by one.

Chef assigns a prefix of these tasks to the first processor and the remaining tasks to the second processor. 

For example, if there are 3 tasks, Chef can do one of the following:
Assign no task to the first processor. This means, the second processor will execute tasks 1, 2 and 3.
Assign task 1 to the first processor. This means, the second processor will execute tasks 2 and 3.
Assign tasks 1 and 2 to the first processor. This means, the second processor will execute task 3.
Assign tasks 1, 2 and 3 to the first processor. Thus, second processor would execute no tasks.

Find the minimum time in which all the tasks can be executed.

------ Input Format ------ 

- First line will contain T, number of test cases. Then the test cases follow.
- The first line of each test case contains a single integer N, the number of tasks waiting to be executed.
- The second line of each test case contains N space separated positive integers A_{1}, A_{2}, \ldots, A_{N} denoting the execution time for each task.

------ Output Format ------ 

For each test case, output in a single line, the minimum time in which all tasks can be executed.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{5}$
- The sum of $N$ over all test cases is not more than $2\cdot 10^{5}$.

------ subtasks ------ 

Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
3
3
4 2 3
6
1 1 1 1 1 1
1
5
----- Sample Output 1 ------ 
5
3
5
----- explanation 1 ------ 
Test Case 1: Chef assigns task $1$ to the first processor and tasks $2$ and $3$ to the second processor. The first processor takes $4$ seconds to execute task $1$. The second processor takes $2+3 = 5$ seconds to execute tasks $2$ and $3$. Thus, atleast $5$ seconds are required to execute all tasks. 

Test Case 2: Chef assigns tasks $1, 2$ and $3$ to the first processor. Processes $4, 5$ ad $6$ are executed by second processor.

Test Case 3: Chef assigns task $1$ to the first processor. No task is executed by second processor.

Difficulty: MEDIUM
Tags: Range queries
Skill types: Range queries

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(p1, p2) = (0, 0)
	(i, j) = (0, n - 1)
	while i < j:
		if p1 < p2:
			p1 += l[i]
			i += 1
		else:
			p2 += l[j]
			j -= 1
	if i == j:
		if p1 < p2:
			p1 += l[i]
		else:
			p2 += l[i]
	print(max(p1, p2))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	start = 0
	end = n - 1
	(p1, p2) = (0, 0)
	while start <= end:
		if p1 < p2:
			p1 = p1 + l[start]
			start = start + 1
		else:
			p2 = p2 + l[end]
			end = end - 1
	if p1 >= p2:
		print(p1)
	else:
		print(p2)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	(s1, s2) = (0, sum(a))
	m = sum(a)
	for i in a:
		s1 += i
		s2 -= i
		m = min(m, max(s1, s2))
		if s1 > s2:
			break
	print(m)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split(' ')))
	cpu_1 = a[0]
	cpu_2 = a[n - 1]
	if n == 1:
		print(cpu_1)
	elif n == 2:
		print(max(cpu_1, cpu_2))
	else:
		(i, j) = (1, n - 2)
		while i <= j:
			if cpu_1 <= cpu_2:
				cpu_1 += a[i]
				i += 1
			else:
				cpu_2 += a[j]
				j -= 1
		print(max(cpu_1, cpu_2))
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	rq = sum(a) / 2
	smm = 0
	l = 0
	for i in a:
		smm += i
		l = i
		if smm > rq:
			break
	sma = 2 * rq
	ans = min(max(smm, sma - smm), max(smm - l, sma + l - smm))
	print(int(ans))


t = int(input())
while t:
	n = int(input())
	list1 = list(map(int, input().split(' ')))
	suma = 0
	sumb = 0
	i = 0
	j = 1
	while i + j <= n:
		if suma <= sumb:
			suma += list1[i]
			i += 1
		else:
			sumb += list1[n - j]
			j += 1
	print(max(suma, sumb))
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	res = 10 ** 10 + 10
	f = 0
	for i in a:
		m = max(s - f, f)
		if m < res:
			res = m
		f += i
	print(res)


for i in range(0, int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	m = 10 ** 10 + 10
	f = 0
	s = sum(li)
	for ele in li:
		i = max(s - f, f)
		if i < m:
			m = i
		f += ele
	print(m)


for _ in range(int(input())):
	N = int(input())
	lst = list(map(int, input().split(' ')))
	s = sum(lst)
	m = 10 ** 10 + 1
	f = 0
	for ele in lst:
		i = max(s - f, f)
		if i < m:
			m = i
		f += ele
	print(m)


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	m = 10 ** 10 + 1
	p1 = 0
	for i in a:
		maxi = max(s - p1, p1)
		if maxi < m:
			m = maxi
		p1 += i
	print(m)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	m = 10 ** 10 + 1
	p1 = 0
	for i in a:
		maxi = max(s - p1, p1)
		if maxi < m:
			m = maxi
		p1 += i
	print(m)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(a[0])
		continue
	if n == 2:
		print(max(a[0], a[1]))
		continue
	p1 = 0
	p2 = 0
	start = 0
	end = n - 1
	while start <= end:
		if p1 >= p2:
			p2 += a[start]
			start = start + 1
		else:
			p1 += a[end]
			end = end - 1
	print(max(p1, p2))


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	tot = sum(A)
	tm = 10 ** 10 + 1
	sp1 = 0
	for a in A:
		m = max(tot - sp1, sp1)
		if m < tm:
			tm = m
		sp1 += a
	print(tm)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	p1 = p2 = []
	s1 = a[0]
	s2 = a[-1]
	b = 0
	c = n - 1
	if len(a) == 1:
		print(a[0])
	else:
		while True:
			if s1 >= s2:
				c -= 1
				s2 += a[c]
			else:
				b += 1
				s1 += a[b]
			if b == c - 1:
				break
		print(max(s1, s2))


for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	sum1 = 0
	s = []
	s1 = sum(l)
	for i in l:
		sum1 += i
		x = max(sum1, s1 - sum1)
		s.append(x)
	print(min(s))


t = int(input())
while t != 0:
	n = int(input())
	l = list(map(int, input().split()))
	s = 0
	cs = 0
	cr = 0
	for i in l:
		s = s + i
	for i in l:
		if cs >= s / 2:
			break
		cs = cs + i
	l.reverse()
	for i in l:
		if cr >= s / 2:
			break
		cr = cr + i
	if cr > cs:
		c = cs
	else:
		c = cr
	if s - c > c:
		print(c)
	else:
		print(c)
	t = t - 1


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	a = 0
	gh = 0
	lh = 0
	for i in l:
		if a + i >= s // 2:
			lh = a
			gh = a + i
			break
		a += i
	if abs(s // 2 - gh) > abs(s // 2 - lh):
		print(s - lh)
	else:
		print(max(s - gh, gh))


t = input()
for c in range(0, int(t)):
	N = int(input())
	A = list(map(int, input().split()))
	if N == 1:
		print(A[0])
		continue
	i = 0
	j = N - 1
	ai = A[0]
	aj = A[-1]
	while j - i != 1:
		if ai > aj:
			j -= 1
			aj += A[j]
		else:
			i += 1
			ai += A[i]
	print(max(ai, aj))


for jj in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	sm = 0
	for _ in k:
		sm += _
	ss = 0
	mn = sm
	for j in range(n):
		ss += k[j]
		mn1 = max(ss, sm - ss)
		if mn1 < mn:
			mn = mn1
	print(mn)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	sumA = sum(A)
	total = 0
	lis = []
	for i in A:
		total += i
		x = max(total, sumA - total)
		lis.append(x)
	print(min(lis))


tst = int(input())
for i in range(tst):
	num = int(input())
	arr = list(map(int, input().split()))
	s1 = 0
	s2 = sum(arr)
	s = []
	ans = 0
	for j in range(num):
		s1 = s1 + arr[j]
		ans = max(s1, s2 - s1)
		s.append(ans)
	print(min(s))


import sys
max_size = sys.maxsize
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		ans = sum(a)
		print(ans)
		continue
	sum_ = sum(a)
	f = 0
	s = 0
	fp = 0
	sp = 0
	final = max_size
	for i in range(0, n):
		fp += a[i]
		sp = sum_ - fp
		ans = max(fp, sp)
		final = min(final, ans)
	print(final)


get_int = lambda : int(input())
get_mint = lambda : list(map(int, input().split()))
for _ in range(get_int()):
	N = get_int()
	A = get_mint()
	if N < 3:
		print(max(A))
		continue
	(prefix, suffix) = (0, sum(A))
	minimal = 10000001
	for Ai in A:
		prefix += Ai
		suffix -= Ai
		if abs(suffix - prefix) < minimal:
			maximal = max(suffix, prefix)
			minimal = abs(suffix - prefix)
			if minimal == 0:
				break
	print(maximal)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a) - a[0]
	t = a[0]
	tmin = max(t, s)
	for i in range(1, n):
		t += a[i]
		s -= a[i]
		t1 = max(t, s)
		if tmin > t1:
			tmin = t1
	print(tmin)


testcase = int(input())
for i in range(testcase):
	numTasks = int(input())
	tasklist = list(map(int, input().split()))
	tot = sum(tasklist)
	minVal = tot
	prefix = 0
	for t1 in tasklist:
		prefix += t1
		prefix2 = tot - prefix
		minVal = min(minVal, max(prefix, prefix2))
	print(minVal)


import sys
for _ in range(int(input())):
	n = int(input())
	a = [int(j) for j in input().split()]
	s = sum(a)
	p1 = 0
	res = 9999999999
	req = 0
	for i in range(n):
		p2 = s - p1
		req = max(p1, p2)
		res = min(req, res)
		p1 += a[i]
	print(res)


import sys
from sys import stdin, stdout
stdint = lambda : int(stdin.readline())
seq = lambda : list(map(int, stdin.readline().strip().split()))
for _ in range(stdint()):
	n = stdint()
	nums = seq()
	total = sum(nums)
	prefix = 0
	minVal = sys.maxsize
	for num in nums:
		prefix += num
		minVal = min(minVal, max(prefix, total - prefix))
	print(minVal)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	(l, r) = (0, n - 1)
	(left_sum, right_sum) = (0, 0)
	while l < n and r > 0 and (l + 1 != r):
		if left_sum + arr[l] < right_sum + arr[r]:
			left_sum += arr[l]
			l += 1
		else:
			right_sum += arr[r]
			r -= 1
	print(max(sum(arr[:l + 1]), sum(arr[r:])))


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	(p1, p2) = (0, 0)
	(l, r) = (0, n - 1)
	while l <= r:
		if p1 <= p2:
			p1 += a[l]
			l += 1
		else:
			p2 += a[r]
			r -= 1
	print(max(p1, p2))


for i in range(int(input())):
	no = int(input())
	li = list(map(int, input().split()))
	i = 0
	j = no - 1
	one = two = 0
	while i <= j:
		if one < two:
			one += li[i]
			i += 1
		else:
			two += li[j]
			j -= 1
	print(max(one, two))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	(s1, s2) = (0, 0)
	(i, j) = (0, n - 1)
	while i <= j:
		if s1 < s2:
			s1 += a[i]
			i += 1
		elif s1 > s2:
			s2 += a[j]
			j -= 1
		else:
			s1 += a[i]
			s2 += a[j]
			i += 1
			j -= 1
	print(max(s1, s2))


t = int(input())
for i in range(t):
	n = int(input())
	x = [int(ww) for ww in input().split()]
	l = []
	w = 0
	q = sum(x)
	for i in range(n):
		w = w + x[i]
		l.append(max(q - w, w))
	print(min(l))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	cur_sum = 0
	total = sum(a)
	ans = total
	for i in a[:len(a) - 1]:
		cur_sum += i
		ans = min(ans, max(total - cur_sum, cur_sum))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	cur_sum = 0
	tot_sum = sum(arr)
	ans = tot_sum
	for i in arr[:len(arr) - 1]:
		cur_sum += i
		ans = min(ans, max(tot_sum - cur_sum, cur_sum))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(p1, p2) = (0, n - 1)
	(sum1, sum2) = (0, 0)
	while p1 <= p2:
		if sum1 < sum2:
			sum1 = sum1 + l[p1]
			p1 += 1
		elif sum1 > sum2:
			sum2 = sum2 + l[p2]
			p2 -= 1
		else:
			sum1 = sum1 + l[p1]
			p1 += 1
			sum2 = sum2 + l[p2]
			p2 -= 1
	print(max(sum1, sum2))


for a in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	t = sum(l)
	p = 0
	ans = t
	for i in l:
		p += i
		p2 = t - p
		r = max(p, p2)
		ans = min(r, ans)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	proc = list(map(int, input().split()))
	tot = sum(proc)
	p1 = 0
	res = tot
	for i in proc:
		p1 += i
		p2 = tot - p1
		time = max(p1, p2)
		res = min(time, res)
	print(res)


for _ in range(int(input())):
	N = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	mini = s
	curr = 0
	for i in range(N):
		curr += l[i]
		mini = min(mini, max(curr, s - curr))
	print(mini)


for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	sm = sum(ar)
	ans = 0
	res = []
	for i in ar:
		ans += i
		res.append(max(ans, sm - ans))
	print(min(res))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(l[0])
	else:
		s = t = sum(l)
		c = 0
		for x in l:
			c += x
			t -= x
			e = max(c, t)
			s = min(e, s)
		print(s)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ele = tot = sum(l)
	st = 0
	for i in l:
		st += i
		tot -= i
		pross = max(st, tot)
		ele = min(ele, pross)
	print(ele)


for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	(P1, P2, res) = (0, 0, max(sum(L), L[0]))
	diff = sum(L) - L[0]
	rem = sum(L)
	for i in range(n):
		P1 += L[i]
		P2 = rem - P1
		if abs(P1 - P2) < diff:
			res = max(P1, P2)
			diff = abs(P1 - P2)
	print(res)


for _ in range(int(input())):
	N = int(input())
	l = list(map(int, input().split()))
	maxi = max(l)
	preA = [0] * N
	postA = [0] * N
	preA[0] = l[0]
	postA[N - 1] = l[N - 1]
	for i in range(1, N):
		preA[i] = preA[i - 1] + l[i]
	for i in range(N - 2, -1, -1):
		postA[i] = postA[i + 1] + l[i]
	mini = postA[0]
	for i in range(N - 1):
		mini = min(mini, max(preA[i], postA[i + 1]))
	print(mini)


def getData(t):
	for _ in range(t):
		N = int(input())
		tasks = list(map(int, input().split()))
		S = sum(tasks)
		print(main(N, tasks, S))

def main(N, tasks, S):
	curr = 0
	ans = S
	for i in range(N):
		curr += tasks[i]
		ans = min(ans, max(curr, S - curr))
	return ans
t = int(input())
getData(t)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(b, c) = (0, 0)
	for i in range(n):
		if b < c:
			b += a[0]
			a.pop(0)
		else:
			c += a[-1]
			a.pop(-1)
	print(max(b, c))


for i in range(int(input())):
	n = int(input())
	tasks = list(map(int, input().split()))
	total_time = sum(tasks)
	p1 = 0
	res = total_time
	for i in tasks:
		p1 += i
		p2 = total_time - p1
		time = max(p1, p2)
		res = min(time, res)
	print(res)


T = int(input())
for t in range(T):
	n = int(input())
	s = input().split(' ')
	a = [int(x) for x in s]
	if n == 1:
		ans = a[0]
	else:
		cur = 0
		sum = 0
		for el in a:
			sum += el
		rem = sum
		for i in range(n):
			cur = cur + a[i]
			if cur > rem:
				ans = max(rem, cur - a[i])
				break
			rem = rem - a[i]
	print(ans)


import sys
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split(' ')]
	if N == 1:
		print(A[0])
		continue
	ans = sys.maxsize
	sm = sum(A)
	a = 0
	for i in range(N):
		a += A[i]
		sm -= A[i]
		ans = min(ans, max(a, sm))
	print(ans)


for _ in range(int(input())):
	N = int(input())
	Array = list(map(int, input().split()))
	PrefixArray = [t for t in range(N)]
	PrefixArray[0] = Array[0]
	for i in range(1, N):
		PrefixArray[i] = PrefixArray[i - 1] + Array[i]
	TotalTime = PrefixArray[len(PrefixArray) - 1]
	Required = max(PrefixArray[0], TotalTime - PrefixArray[0])
	for element in PrefixArray:
		if max(element, TotalTime - element) < Required:
			Required = max(element, TotalTime - element)
	print(Required)


for t in range(int(input())):
	N = int(input())
	Time = list(map(int, input().split()))
	if len(Time) == 1:
		print(Time[0])
		continue
	maxtime = []
	Total = sum(Time)
	psum = [0] * len(Time)
	psum[0] = Time[0]
	for i in range(1, len(Time)):
		psum[i] = psum[i - 1] + Time[i]
	i = 0
	minimum = float('inf')
	while i < len(Time) - 1:
		firstprocessor = psum[i]
		secondprocessor = Total - firstprocessor
		maximum = max(firstprocessor, secondprocessor)
		if minimum > maximum:
			minimum = maximum
		i = i + 1
	print(minimum)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	i = 0
	j = len(arr) - 1
	x = arr[i]
	y = arr[j]
	while j - i > 1:
		if x < y:
			i += 1
			x += arr[i]
		else:
			j -= 1
			y += arr[j]
	print(max(x, y))


def task(a, n):
	sm1 = 0
	sm2 = sum(a)
	mn = abs(sm1 - sm2)
	time = max(sm1, sm2)
	for i in range(n):
		sm1 += a[i]
		sm2 -= a[i]
		cu = abs(sm2 - sm1)
		if cu < mn:
			mn = cu
			time = max(sm1, sm2)
	print(time)
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	task(a, n)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	total_time = sum(arr)
	p1 = 0
	res = total_time
	for i in arr:
		p1 += i
		p2 = total_time - p1
		time = max(p1, p2)
		res = min(time, res)
	print(res)


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(l[0])
	else:
		p1 = 0
		p2 = 0
		(x, y) = (0, n - 1)
		while x <= y:
			if p1 > p2:
				p2 += l[y]
				y -= 1
			else:
				p1 += l[x]
				x += 1
		print(max(p1, p2))
	t -= 1


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	p1 = 0
	p2 = sum(arr)
	for j in arr:
		if max(p1 + j, p2 - j) < max(p1, p2):
			p1 += j
			p2 -= j
		else:
			break
	print(max(p1, p2))


for i in range(int(input())):
	n = int(input())
	li = list(map(int, input().split(' ')))
	(i, j) = (0, n - 1)
	(itime, jtime) = (0, 0)
	while i <= j:
		if itime > jtime:
			jtime += li[j]
			j -= 1
		else:
			itime += li[i]
			i += 1
	print(max(itime, jtime))


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	sum_ = sum(li)
	half_sum = sum_ // 2
	adding = 0
	for j in li:
		prev = adding
		adding += j
		if adding > half_sum:
			print(min(sum_ - prev, adding))
			break


for i in range(int(input())):
	a = int(input())
	list1 = list(map(int, input().split()))
	j = 0
	k = a - 1
	sum1 = 0
	sum2 = 0
	while True:
		if sum1 <= sum2:
			sum1 += list1[j]
			if j == k:
				break
			j += 1
		else:
			sum2 += list1[k]
			if j == k:
				break
			k -= 1
	if sum1 >= sum2:
		print(sum1)
	else:
		print(sum2)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	summ = sum(l)
	L = []
	sum_ = 0
	for i in range(n):
		sum_ = sum_ + l[i]
		k = max(sum_, summ - sum_)
		L.append(k)
	L.append(summ)
	print(min(L))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	_sum = sum(arr)
	arr_time = [_sum]
	_sum1 = 0
	for i in range(n - 1):
		_sum1 += arr[i]
		arr_time.append(max(_sum1, _sum - _sum1))
	print(min(arr_time))


T = int(input())
while T != 0:
	N = int(input())
	tt = [int(x) for x in input().split()]
	i = 0
	j = N - 1
	pA = 0
	pB = 0
	while i <= j:
		if pA > pB:
			pB += tt[j]
			j -= 1
		else:
			pA += tt[i]
			i += 1
	print(max(pA, pB))
	T -= 1