You are given a sequence $A_1, A_2, \ldots, A_N$. For each $k$ ($1 \le k \le N$), let's define a function $f(k)$ in the following way:
- Consider a sequence $B_1, B_2, \ldots, B_N$, which is created by setting $A_k = 0$. Formally, $B_k = 0$ and $B_i = A_i$ for each valid $i \neq k$.
- $f(k)$ is the number of ways to split the sequence $B$ into two non-empty contiguous subsequences with equal sums.
Find the sum $S = f(1) + f(2) + \ldots + f(N)$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing one integer — the sum $S$.

-----Constraints-----
- $1 \le T \le 10$
- $2 \le N \le 2 \cdot 10^5$
- $1 \le |A_i| \le 10^9$ for each valid $i$

-----Example Input-----
2
6
1 2 1 1 3 1
3
4 1 4

-----Example Output-----
6
2

Source: codechef | Difficulty: VERY_HARD
Tags: Data structures

Constructive algorithms


Solutions:
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	total = sum(a)
	prefix = 0
	d = Counter()
	for i in range(n):
		remains = total - a[i]
		if not remains % 2:
			ans += d[remains // 2]
		prefix += a[i]
		d[prefix] += 1
	d.clear()
	suffix = 0
	for i in range(n - 1, -1, -1):
		remains = total - a[i]
		if not remains % 2:
			ans += d[remains // 2]
		suffix += a[i]
		d[suffix] += 1
	print(ans)


from collections import defaultdict
t = int(input())
queries = []
while t:
	t -= 1
	n = int(input())
	queries.append(list(map(int, input().split())))

def solve(a, n):
	su = sum(a)
	mp = defaultdict(int)
	s = 0
	ans = 0
	for i in range(n):
		if (su - a[i]) % 2 == 0:
			ans += mp[(su - a[i]) // 2]
		s += a[i]
		mp[s] += 1
	mp.clear()
	s = 0
	for i in range(n - 1, -1, -1):
		if (su - a[i]) % 2 == 0:
			ans += mp[(su - a[i]) // 2]
		s += a[i]
		mp[s] += 1
	return ans
for i in queries:
	print(solve(i, len(i)))


import bisect
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	total = sum(a)
	diff = {}
	inter_sum = 0
	for i in range(n - 1):
		if a[i] == 0:
			continue
		inter_sum += a[i]
		c = inter_sum - (total - inter_sum)
		if c in list(diff.keys()):
			diff[c].append(i)
		else:
			diff[c] = [i]
	count = 0
	for i in range(n):
		if -a[i] in list(diff.keys()):
			ans = bisect.bisect_left(diff[-a[i]], i)
			count += ans
		if a[i] in list(diff.keys()):
			ans = bisect.bisect_left(diff[a[i]], i)
			count += len(diff[a[i]]) - ans
	print(count)


from sys import stdin

def gt(num):
	if num:
		return num
	return 0
for __ in range(int(stdin.readline().split()[0])):
	n = int(stdin.readline().split()[0])
	a = list(map(int, stdin.readline().split()))
	cnta = dict()
	cnta.setdefault(0)
	cntb = dict()
	cntb.setdefault(0)
	for i in a:
		cnta[i] = gt(cnta.get(i)) + 1
	asum = 0
	bsum = sum(a)
	ans = 0
	for i in range(n - 1):
		asum += a[i]
		bsum -= a[i]
		cnta[a[i]] = gt(cnta.get(a[i])) - 1
		cntb[a[i]] = gt(cntb.get(a[i])) + 1
		ans += gt(cnta.get(bsum - asum))
		ans += gt(cntb.get(asum - bsum))
	print(ans)


def abc(l, val):
	i = 0
	j = len(l) - 1
	s = -1
	while i <= j:
		mid = i + (j - i) // 2
		if l[mid] < val:
			s = mid
			i = mid + 1
		else:
			j = mid - 1
	return s + 1

def bca(l, val):
	i = 0
	j = len(l) - 1
	s = len(l)
	while i <= j:
		mid = i + (j - i) // 2
		if l[mid] >= val:
			s = mid
			j = mid - 1
		else:
			i = mid + 1
	m = 0
	return len(l) - s
import random
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	x = sum(l)
	ans = 0
	k = [l[0]]
	for i in range(1, n):
		k.append(k[-1] + l[i])
	d = {}
	for i in range(n):
		try:
			d[k[i]] += [i]
		except:
			d[k[i]] = [i]
	for i in range(n):
		s = x - l[i]
		if not s % 2:
			try:
				c = d[s // 2]
				ans += abc(c, i)
			except:
				pass
			try:
				c = d[s // 2 + l[i]]
				ans += bca(c, i)
				if k[-1] == s // 2 + l[i]:
					ans -= 1
			except:
				pass
	print(ans)


from collections import Counter

def result(a, n):
	ans = 0
	total = sum(a)
	prefix = 0
	d = Counter()
	for i in range(n):
		remains = total - a[i]
		if not remains % 2:
			ans += d[remains // 2]
		prefix += a[i]
		d[prefix] += 1
	d.clear()
	suffix = 0
	for i in range(n - 1, -1, -1):
		remains = total - a[i]
		if not remains % 2:
			ans += d[remains // 2]
		suffix += a[i]
		d[suffix] += 1
	return ans
queries = []
for _ in range(int(input())):
	n = input()
	queries.append(list(map(int, input().split())))
for q in queries:
	print(result(q, len(q)))