Read problems statements in mandarin chinese, russian and vietnamese as well. 

Our little chef is fond of doing additions/sums in his free time. Today, he has an array A consisting of N positive integers and he will compute prefix and suffix sums over this array.

He first defines two functions prefixSum(i) and suffixSum(i) for the array as follows. The function prefixSum(i) denotes the sum of first i numbers of the array. Similarly, he defines suffixSum(i) as the sum of last N - i + 1 numbers of the array. 

Little Chef is interested in finding the minimum index i for which the value prefixSum(i) + suffixSum(i) is the minimum. In other words, first you should minimize the value of prefixSum(i) + suffixSum(i), and then find the least index i for which this value is attained.

Since, he is very busy preparing the dishes for the guests, can you help him solve this problem?

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains a single integer N denoting the number of integers in the array A.
The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the array A.

------ Output ------ 

For each test case, output a single line containing the answer.

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

$1 ≤ T ≤ 10$
$1 ≤ N, A[i] ≤ 10^{5}$

------ Subtasks ------ 

	$Subtask #1 : (20 points)  1 ≤ N ≤ 100$
	$Subtask #2 : (80 points)  Original constraints$

----- Sample Input 1 ------ 
2

3

1 2 3

4

2 1 3 1
----- Sample Output 1 ------ 
1

2
----- explanation 1 ------ 
Example case 1. Let's calculate prefixSum(i) + suffixSum(i) for all indexes i in the sample case.

prefixSum(1) + suffixSum(1) = 1 + 6 = 7
prefixSum(2) + suffixSum(2) = 3 + 5 = 8
prefixSum(3) + suffixSum(3) = 6 + 3 = 9

The minimum value of the function is 7, which is attained at index 1, so the answer would be 1.

Example case 2. Let's calculate prefixSum(i) + suffixSum(i) for all indexes i in the sample case.

prefixSum(1) + suffixSum(1) = 2 + 7 = 9
prefixSum(2) + suffixSum(2) = 3 + 5 = 8
prefixSum(3) + suffixSum(3) = 6 + 4 = 10
prefixSum(4) + suffixSum(4) = 7 + 1 = 8

The minimum value of the function is 8, which is achieved for indices 2 and 4. The minimum of these two indices 2, 4 is index 2. Hence, the answer will be 2.

Difficulty: EASY
Tags: Range queries
Skill types: Range queries

Starter code:

Solutions:
T = int(input())
for i in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	print(A.index(min(A)) + 1)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(l.index(min(l)) + 1)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	y = min(arr)
	res = arr.index(y)
	print(res + 1)


b = int(input())
for i in range(b):
	N = int(input())
	a = list(map(int, input().split()))
	b = a[0]
	for i in a:
		if b > i:
			b = i
	print(a.index(b) + 1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	y = min(a)
	res = a.index(y)
	print(res + 1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(a.index(min(a)) + 1)


for tc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ind = -1
	minele = 100000000
	for (i, ele) in enumerate(arr):
		if ele < minele:
			minele = min(minele, ele)
			ind = i
	print(ind + 1)


for i in range(int(input())):
	N = int(input())
	L = list(map(int, input().split()))
	print(L.index(min(L)) + 1)


t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(a.index(min(a)) + 1)


T = int(input())
for j in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	P1 = A[0]
	P2 = sum(A)
	P = P1 + P2
	S = 1
	for i in range(1, N):
		P1 += A[i]
		P2 -= A[i - 1]
		if P1 + P2 < P:
			P = P1 + P2
			S = i + 1
	print(S)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	pres = a[0]
	susum = sum(a)
	m = a[0] + sum(a)
	res = 1
	for i in range(1, n):
		pres += a[i]
		susum -= a[i - 1]
		if pres + susum < m:
			m = pres + susum
			res = i + 1
	print(res)


for i in range(int(input())):
	n = int(input())
	arr = [int(k) for k in input().split()]
	pres = arr[0]
	susum = sum(arr)
	m = arr[0] + sum(arr)
	res = 1
	for i in range(1, n):
		pres += arr[i]
		susum -= arr[i - 1]
		if pres + susum < m:
			m = pres + susum
			res = i + 1
	print(res)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	k = a.index(min(a))
	print(k + 1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	ans = l.index(min(l))
	print(ans + 1)


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	suff = sum(l)
	prev = l[0]
	m = prev + suff
	suff = suff - l[0]
	ans = 0
	for i in range(1, n):
		prev = prev + l[i]
		if prev + suff < m:
			ans = i
			m = prev + suff
		suff -= l[i]
	print(ans + 1)


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	print(b.index(min(b)) + 1)


for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	x = b.index(min(b)) + 1
	print(x)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(a.index(min(a)) + 1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ps = [0] * n
	ss = [0] * n
	ps[0] = a[0]
	ss = []
	b = []
	for i in range(1, n):
		ps[i] = ps[i - 1] + a[i]
	summ = 0
	for j in range(n - 1, -1, -1):
		summ += a[j]
		ss.append(summ)
	ss.reverse()
	for k in range(0, n):
		b.append(ps[k] + ss[k])
	c = min(b)
	for j in range(0, len(b)):
		if b[j] == c:
			print(j + 1)
			break


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	x = a.index(min(a)) + 1
	print(x)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = 100000
	i = 0
	for j in range(n):
		if l[j] < s:
			s = l[j]
			i = j + 1
	print(i)


for i in range(int(input())):
	n = int(input())
	a = [int(num) for num in input().split()]
	m = a[0]
	m1 = 0
	for j in range(1, n):
		if a[j] < m:
			m = a[j]
			m1 = j
	print(m1 + 1)


def prefixSum(a):
	b = []
	c = 0
	for i in a:
		c += i
		b.append(c)
	return b

def suffixSum(a):
	b = [0] * len(a)
	c = 0
	for i in range(len(a) - 1, -1, -1):
		c += a[i]
		b[i] = c
	return b
for i in range(int(input())):
	t = int(input())
	a = list(map(int, input().split()))
	q = prefixSum(a)
	r = suffixSum(a)
	d = []
	for i in range(len(a)):
		d.append(q[i] + r[i])
	print(d.index(min(d)) + 1)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	prefix_sum = [0 for i in range(10 ** 5)]
	suffix_sum = [0 for i in range(10 ** 5)]
	prefix_sum[0] = l[0]
	suffix_sum[n - 1] = l[n - 1]
	for i in range(1, n):
		prefix_sum[i] = prefix_sum[i - 1] + l[i]
	for i in range(n - 2, -1, -1):
		suffix_sum[i] = suffix_sum[i + 1] + l[i]
	index = -1
	mini_sum = float('inf')
	for i in range(n):
		s = prefix_sum[i] + suffix_sum[i]
		if s < mini_sum:
			mini_sum = s
			index = i + 1
	print(index)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = min(a)
	index = a.index(m)
	print(index + 1)


n = int(input())
for i in range(n):
	x = int(input())
	l = [int(i) for i in input().split()]
	t = []
	s = sum(l)
	p = 0
	for i in range(x):
		p = p + l[i]
		r = p + s
		t.append(r)
		s = s - l[i]
	m = min(t)
	print(t.index(m) + 1)


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()][:n]
	summ = 0
	pre = []
	suf = []
	res = []
	for i in l:
		summ += i
		pre.append(summ)
	summation = sum(l)
	for i in l:
		a = summation + i
		suf.append(a)
	m = min(suf)
	print(suf.index(m) + 1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(ps, ss) = ([], [])
	summ = []
	summation = sum(a) + a[0]
	for i in range(n):
		ps.append(a[i])
		ss.append(summation - a[i])
		summation -= a[i]
	summ = ps + ss
	mini = min(summ)
	print(summ.index(mini) + 1)


import math

def prefixSum(A, i):
	return sum(A[:i])

def suffixSum(A, i):
	return sum(A[i - 1:])
T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	m = min(A)
	index = A.index(m)
	print(index + 1)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mis = min(a)
	ans = a.index(mis) + 1
	print(ans)


for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	cook = b[0]
	index = 0
	for i in range(1, a):
		if b[i] < cook:
			cook = b[i]
			index = i
	print(index + 1)


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	k = s.index(min(s))
	print(k + 1)


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	pref = 0
	suff = 0
	l = []
	for i in range(n):
		p = suff - pref
		pref += s[i]
		l.append(p + pref)
	m = min(l)
	for i in range(len(l)):
		if l[i] == m:
			print(i + 1)
			break


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	k = s + l[0]
	m = 0
	for i in range(1, n):
		p = s + l[i]
		if p < k:
			m = i
			k = p
	print(m + 1)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	s = sum(a)
	mini = 100000000000.0
	ind = -1
	for i in range(n):
		if s + a[i] < mini:
			mini = s + a[i]
			ind = i + 1
	print(ind)


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	ps = [0 for i in range(n + 1)]
	ss = [0 for i in range(n + 1)]
	for i in range(n):
		ps[i + 1] = ps[i] + a[i]
		ss[n - 1 - i] = ss[n - i] + a[n - 1 - i]
	(res, m) = (1, ps[1] + ss[0])
	for i in range(2, n + 1):
		s = ps[i] + ss[i - 1]
		if s < m:
			res = i
			m = s
	print(res)


for _ in range(int(input())):
	N = int(input())
	X = list(map(int, input().split()))
	print(X.index(min(X)) + 1)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = min(a)
	ind = a.index(m)
	print(ind + 1)


t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	m = min(l)
	print(l.index(m) + 1)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input('').split()))
	sum1 = sum(l)
	l2 = []
	for j in range(len(l)):
		l2.append(sum1 + l[j])
		sum1 = sum1 - l[j]
	print(l.index(min(l)) + 1)


t = int(input())
for _ in range(t):
	n = int(input())
	m = list(map(int, input().split()))
	print(m.index(min(m)) + 1)


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	print(l.index(min(l)) + 1)
	t -= 1


t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	a = [int(i) for i in input().split()]
	psum = []
	ans = []
	xor = 0
	for i in range(len(a)):
		xor += a[i]
		psum.append(xor)
	for i in range(len(a)):
		if i == 0 or i == len(a) - 1:
			c = a[i] + psum[len(a) - 1]
			ans.append(c)
		else:
			c = psum[i] + psum[len(a) - 1] - psum[i - 1]
			ans.append(c)
	minimum = min(ans)
	print(ans.index(minimum) + 1)