Eugene likes working with arrays. And today he needs your help in solving one challenging task.

An array $c$ is a subarray of an array $b$ if $c$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Let's call a nonempty array good if for every nonempty subarray of this array, sum of the elements of this subarray is nonzero. For example, array $[-1, 2, -3]$ is good, as all arrays $[-1]$, $[-1, 2]$, $[-1, 2, -3]$, $[2]$, $[2, -3]$, $[-3]$ have nonzero sums of elements. However, array $[-1, 2, -1, -3]$ isn't good, as his subarray $[-1, 2, -1]$ has sum of elements equal to $0$.

Help Eugene to calculate the number of nonempty good subarrays of a given array $a$.


-----Input-----

The first line of the input contains a single integer $n$ ($1 \le n \le 2 \times 10^5$)  — the length of array $a$.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$)  — the elements of $a$. 


-----Output-----

Output a single integer  — the number of good subarrays of $a$.


-----Examples-----
Input
3
1 2 -3

Output
5

Input
3
41 -41 41

Output
3



-----Note-----

In the first sample, the following subarrays are good: $[1]$, $[1, 2]$, $[2]$, $[2, -3]$, $[-3]$. However, the subarray $[1, 2, -3]$ isn't good, as its subarray $[1, 2, -3]$ has sum of elements equal to $0$.

In the second sample, three subarrays of size 1 are the only good subarrays. At the same time, the subarray $[41, -41, 41]$ isn't good, as its subarray $[41, -41]$ has sum of elements equal to $0$.

Difficulty: MEDIUM_HARD
Tags: Sorting

Amortized analysis

Data structures

Implementation
Skill types: Data structures

Sorting

Amortized analysis

Starter code:

Solutions:
import math

def main():
	sums = dict()
	sums[0] = -1
	pos = dict()
	pos[-1] = 0
	n = int(input())
	a = list(map(int, input().split()))
	cur = 0
	st = -1
	sm = 0
	for i in range(n):
		cur += a[i]
		if not cur in sums:
			sums[cur] = i
			pos[i] = cur
			sm += i - st
		elif cur in sums:
			for k in range(st, sums[cur]):
				del sums[pos[k]]
				del pos[k]
			st = sums[cur] + 1
			sums[cur] = i
			pos[i] = cur
			sm += i - st
	print(sm)
t = 1
for i in range(t):
	main()


import sys

def fastio():
	from io import StringIO
	from atexit import register
	global input
	sys.stdin = StringIO(sys.stdin.read())
	input = lambda : sys.stdin.readline().rstrip('\r\n')
	sys.stdout = StringIO()
	register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()
I = lambda : list(map(int, input().split()))
n = int(input())
l = I()
an = 0
p = 0
h = {}
s = 0
c = -1
for i in range(n):
	s += l[i]
	a = h.get(s, -1)
	if a != -1 and a >= c:
		an += (a - c + 1) * (n - i)
		c = a + 1
	if s == 0 and an == 0:
		an += n - i
		c = 0
	h[s] = i
print(n * (n + 1) // 2 - an)


from itertools import accumulate
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
cum = [0] + list(accumulate(a))
s = t = 0
ans = 0
st = set()
while s <= n:
	while t <= n and cum[t] not in st:
		st.add(cum[t])
		t += 1
	ans += t - s - 1
	st.remove(cum[s])
	s += 1
print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
n = list(map(int, input().split()))[0] + 1
a = list(map(int, input().split()))
s = [0]
st = set()
beg = 0
end = 0
ans = 0
for i in range(len(a)):
	s.append(a[i] + s[-1])
s.append(s[-1])
while True:
	if beg == n:
		print(ans)
		break
	if len(st) == end - beg:
		st.add(s[end])
		end += 1
	else:
		ans += end - beg - 2
		if s[end - 1] != s[beg]:
			st.remove(s[beg])
		beg += 1


import io
import os
from collections import deque

def solve(N, A):
	cumsum = [0]
	for x in A:
		cumsum.append(cumsum[-1] + x)
	ans = 0
	window = deque([0])
	windowSet = set([0])
	for j in range(N + 1):
		while cumsum[j] in windowSet:
			i = window.popleft()
			windowSet.remove(cumsum[i])
		window.append(j)
		windowSet.add(cumsum[j])
		ans += len(window) - 1
	return ans
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = solve(N, A)
print(ans)


n = int(input())
a = [0] + [int(i) for i in input().split()]
(m, s, result) = (0, 0, 0)
d = {}
for i in range(n + 1):
	s += a[i]
	if s in d:
		m = max(m, d[s] + 1)
	result += i - m
	d[s] = i
print(result)


n = int(input())
l = list(map(int, input().split()))
s = set()
s.add(0)
pre = [0]
for i in range(n):
	pre.append(pre[-1] + l[i])
i = 0
j = 0
ans = 0
while i < n:
	while j < n and pre[j + 1] not in s:
		j += 1
		s.add(pre[j])
	ans += j - i
	if pre[i] in s:
		s.remove(pre[i])
	i += 1
print(ans)


from collections import defaultdict
from sys import stdin, stdout

def write(_s):
	stdout.write(_s)

def writeint(_s):
	stdout.write(str(_s))

def writelist(_l):
	stdout.write(''.join(_l))

def read():
	return stdin.readline().strip().split(' ')

def readint():
	return int(stdin.readline().strip())

def readints():
	return map(int, stdin.readline().strip().split(' '))
n = readint()
a = list(readints())
pref = [0] * (n + 1)
for i in range(0, n):
	pref[i + 1] = pref[i] + a[i]
counter = defaultdict(int)
ok_subarrays = 0
back = 0
for front in range(n + 1):
	counter[pref[front]] += 1
	while counter[pref[front]] > 1:
		counter[pref[back]] -= 1
		back += 1
	ok_subarrays += front - back
writeint(ok_subarrays)


import bisect, collections

def solution():
	n = int(input().strip())
	a = [int(x) for x in input().strip().split()]
	d = collections.defaultdict(list)
	cur = 0
	for i in range(n):
		cur += a[i]
		d[cur].append(i)
	(zeros, prefix, minIdx) = (0, sum(a), n)
	firstFind = True
	for i in range(len(a) - 1, -1, -1):
		prefix -= a[i]
		if prefix in d:
			idx = bisect.bisect_left(d[prefix], i)
			idx = d[prefix][idx] if idx < len(d[prefix]) else n
			minIdx = min(minIdx, idx)
		zeros += n - minIdx
	print(n * (n + 1) // 2 - zeros)

def main():
	for _ in range(1):
		solution()
main()


n = int(input())
ls = [int(x) for x in input().split()]
presum = [0]
for e in ls:
	presum.append(e + presum[-1])
height = {}
ints = []
for (i, s) in enumerate(presum):
	if s not in height:
		height[s] = i - 1
	else:
		ints.append((height[s], i - 1))
		height[s] = i - 1
ints.append((len(ls), len(ls)))
ints = sorted(ints, key=lambda x: x[1])
pos = 0
c = 0
for p in range(len(ls)):
	while p > ints[pos][0] + 1:
		pos += 1
	c += ints[pos][1] - p
print(c)


n = int(input())
arr = [int(x) for x in input().split()]
arr.insert(0, 0)
mp = {0: 0}
sol = n * (n + 1) // 2
acum = 0
index = -1
for i in range(1, n + 1):
	acum += arr[i]
	if acum in mp:
		index = max(index, mp[acum])
	mp[acum] = i
	sol -= index + 1
print(sol)


n = int(input())
a = [int(x) for x in input().split()]
for i in range(1, n):
	a[i] += a[i - 1]
dic = {}
dic[0] = 0
ans = 0
maximum = -1
for i in range(n):
	val = dic.get(a[i], -1)
	maximum = max(maximum, val)
	ans += i - maximum
	dic[a[i]] = i + 1
print(ans)


k = {0}
rez = 0
n = int(input())
a = input().split(' ')
p = [0]
for i in range(n):
	a[i] = int(a[i])
	p.append(p[i] + a[i])
i = 0
j = 0
while i < n:
	while j < n and p[j + 1] not in k:
		j += 1
		k.add(p[j])
	rez += j - i
	k.remove(p[i])
	i += 1
print(rez)


import sys
import math, bisect
sys.setrecursionlimit(10 ** 5)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
I = lambda : int(sys.stdin.readline())
neo = lambda : map(int, sys.stdin.readline().split())
Neo = lambda : list(map(int, sys.stdin.readline().split()))
n = I()
A = Neo()
A = list(accumulate(A))
d = defaultdict(int)
d[0] = -1
Ans = 0
t = -1
for i in range(n):
	if A[i] in d:
		t = max(t, d[A[i]] + 1)
	d[A[i]] = i
	Ans += i - t
print(Ans)


import sys
n = int(sys.stdin.readline())
a = [int(i) for i in sys.stdin.readline().split()]
sums = {0: 0}
s = 0
good = 0
last_good = 0
for (i, val) in enumerate(a):
	s += val
	if s in sums:
		last_good = max(sums[s] + 1, last_good)
	sums[s] = i + 1
	good += 1 + i - last_good
print(good)


import sys, io, os
input = sys.stdin.readline
inputt = lambda : range(int(input()))
inputn = lambda n=1: range(n)
inputi = lambda : map(int, input().split())
inputl = lambda : list(inputi())
from math import *
from heapq import *
from bisect import *
from functools import reduce, lru_cache
from collections import Counter, defaultdict
from builtins import *
MOD = 10 ** 9 + 7

def main():
	for _ in inputn():
		(n,) = inputi()
		A = inputl()
		S = defaultdict(list)
		S[0].append(0)
		s = 0
		l = -1
		t = 0
		for (i, a) in enumerate(A, 1):
			s += a
			if s in S:
				l = max(l, S[s][-1])
			S[s].append(i)
			t += i - l - 1
		print(t)
main()


from sys import stdin
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
ans = [0] * n
sums = list()
sums.append(0)
for i in range(n):
	sums.append(sums[i] + a[i])
ans = 0
ri = 0
s = set()
done = False
for i in range(n):
	for j in range(ri, n + 1):
		if sums[j] in s:
			ri = j
			ans += ri - i - 1
			s.remove(sums[i])
			break
		s.add(sums[j])
		if j == n:
			ri = j + 1
			done = True
	if done:
		ans += ri - i - 1
print(ans)


import sys
from collections import Counter
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

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

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

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():
	n = II()
	aa = LI()
	ss = [0]
	for a in aa:
		ss.append(ss[-1] + a)
	ans = 0
	si = {0: 0}
	j = 0
	for i in range(1, n + 1):
		s = ss[i]
		if s in si and si[s] + 1 > j:
			j = si[s] + 1
		si[s] = i
		ans += i - j
	print(ans)
main()


n = int(input())
a = [0] + [int(x) for x in input().split()]
storage = {}
sump = 0
tota = 0
bgning = 0
for i in range(n + 1):
	sump += a[i]
	if sump in storage:
		bgning = max(bgning, storage[sump] + 1)
	tota += i - bgning
	storage[sump] = i
print(tota)


n = int(input())
a = [0] + list(map(int, input().split()))
(summ, mx, ans) = (0, 0, 0)
d = dict()
for i in range(0, n + 1):
	summ += a[i]
	if summ in d:
		mx = max(mx, d[summ] + 1)
	ans += i - mx
	d[summ] = i
print(ans)


n = int(input())
a = [int(i) for i in input().split()]
good = 0
sums = {0: -1}
su = 0
ind = -1
for i in range(n):
	su += a[i]
	if su in sums:
		ind = max(ind, sums[su] + 1)
	sums[su] = i
	good += i - ind
print(good)


import sys
from itertools import accumulate

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
N = INT()
A = LIST()
acc = [0] + list(accumulate(A))
D = {}
R = [N] * N
for (i, a) in enumerate(acc):
	if a in D:
		R[D[a]] = i - 1
	D[a] = i
R = list(accumulate(R[::-1], min))[::-1]
ans = 0
for i in range(N):
	ans += R[i] - i
print(ans)


n = int(input())
u = list(map(int, input().split()))
d = dict()
p = []
d[u[0]] = 0
if u[0] == 0:
	p.append((0, 0))
else:
	d[0] = -1
w = [0] * n
for i in range(1, n):
	u[i] += u[i - 1]
	if u[i] in d.keys():
		(st, fn) = (d[u[i]] + 1, i)
		p.append((st, fn))
		w[fn] = len(p)
	d[u[i]] = i
m = len(p)
pp = [True] * m
op = -1
for i in range(n):
	if w[i] == 0:
		continue
	if op == -1:
		op = w[i]
	elif p[w[i] - 1][0] < p[op - 1][0]:
		pp[w[i] - 1] = False
	else:
		op = w[i]
px = []
for i in range(m):
	if pp[i]:
		px.append(p[i])
sm = n * (n + 1) // 2
px.append((n, n))
for i in range(len(px) - 1):
	sm -= (px[i][0] + 1) * (px[i + 1][1] - px[i][1])
print(sm)


def read_int():
	return int(input().strip())

def read_ints():
	return list(map(int, input().strip().split(' ')))

def solve():
	n = read_int()
	arr = read_ints()
	prefix = 0
	G = {0: -1}
	segments = []
	for (i, a) in enumerate(arr):
		prefix += a
		if prefix in G:
			segments.append((i, G[prefix] + 1))
		G[prefix] = i
	segments.sort()
	earliest_start = -1
	T = 0
	j = -1
	for i in range(n):
		while j + 1 < len(segments) and segments[j + 1][0] <= i:
			j += 1
			(end, start) = segments[j]
			if start > earliest_start:
				earliest_start = start
		T += i - earliest_start
	return T
print(solve())


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import bisect
from collections import defaultdict
n = int(input())
vals = list(map(int, input().split()))
ans = 0
prefsum = [0]
d1 = defaultdict(list)
for s in range(n):
	prefsum.append(prefsum[-1] + vals[s])
ind = []
dict1 = defaultdict(int)
for s in range(n + 1):
	br = False
	if s == 0:
		for b in range(n + 1):
			if dict1[prefsum[b]] < 1:
				dict1[prefsum[b]] = 1
			else:
				ind.append(b - 1)
				br = True
				break
		if br == False:
			ind.append(n)
	else:
		for b in range(ind[-1] + 1, n + 1):
			if dict1[prefsum[b]] < 1:
				dict1[prefsum[b]] += 1
			else:
				ind.append(b - 1)
				br = True
				break
		if br == False:
			ind.append(n)
	ans += ind[-1] - s
	dict1[prefsum[s]] -= 1
print(ans)


import sys
from collections import defaultdict as df
dir = {'N': (0, 1), 'S': (0, -1), 'E': (1, 0), 'W': (-1, 0)}
cin = sys.stdin.buffer.readline
for _ in range(1):
	n = int(cin())
	ans = 0
	a = list(map(int, cin().split()))
	pref = [0]
	for el in a:
		pref.append(el + pref[-1])
	d = df(int)
	end = -1
	for i in range(1, n + 1):
		while end + 1 < n + 1 and d[pref[end]] < 2:
			end += 1
			d[pref[end]] += 1
		if end < n + 1 and d[pref[end]] < 2:
			end += 1
		d[pref[i - 1]] -= 1
		ans += end - i
	print(ans)


n = int(input())
l = list(map(int, input().split()))
x = [0] * (n + 1)
d = dict()
for i in range(n):
	x[i + 1] = x[i + 1] + x[i] + l[i]
s = 0
c = 0
for i in range(n + 1):
	if x[i] in d:
		d[x[i]] += 1
	else:
		d[x[i]] = 1
	while d[x[i]] > 1:
		d[x[c]] -= 1
		c = c + 1
	s = s + (i - c + 1)
print(s - n - 1)


def solution(n, array):
	memo = {0: 0}
	addptr = 0
	maxptr = 0
	ans = 0
	for i in range(1, n + 1):
		addptr += array[i]
		if addptr in memo:
			maxptr = max(maxptr, memo[addptr] + 1)
		memo[addptr] = i
		ans += i - maxptr
	return ans
print(solution(int(input()), [0] + list(map(int, input().split()))))


from collections import defaultdict
n = int(input())
l = list(map(int, input().split()))
d = defaultdict(int)
ma = -1
ans = 0
su = 0
d[su] = 0
s = set()
s.add(0)
for i in range(n):
	su += l[i]
	if su not in s:
		s.add(su)
		d[su] = i + 1
		continue
	else:
		if d[su] <= ma:
			continue
		else:
			ans += (d[su] - ma) * (n - i)
			ma = max(ma, d[su])
		s.add(su)
		d[su] = i + 1
print(n * (n + 1) // 2 - ans)


def f():
	n = int(input())
	A = [int(s) for s in input().split()]
	S = [0] * (n + 1)
	memo = {0: [0, 0]}
	sum = 0
	for i in range(1, n + 1):
		sum += A[i - 1]
		S[i] = sum
		if sum not in memo:
			memo[sum] = [0]
		memo[sum].append(i)
	ans = 0
	ok = -1
	for (i, s) in enumerate(S):
		a = memo[s]
		a[0] += 1
		if a[0] == 1:
			ans += i - ok - 1
		else:
			ok = max(ok, a[a[0] - 1])
			ans += i - ok - 1
	print(ans)
f()


import sys
input = sys.stdin.readline
a = int(input())
b = list(map(int, input().split()))
c = [0]
su = 0
for i in b:
	su += i
	c.append(su)
ans = 0
thing = {}
temp = 0
for i in range(a + 1):
	if i != 0:
		try:
			temp = min(i - thing[c[i]] - 1, temp + 1)
			ans += temp
		except:
			temp = min(i, temp + 1)
			ans += temp
	thing[c[i]] = i
print(str(ans) + '\n')


from collections import defaultdict
n = int(input())
a = [int(x) for x in input().split()]
d = defaultdict(lambda : -1)
bad = [0] * n
s = 0
maxl = -1
d[0] = 0
for i in range(len(a)):
	s += a[i]
	maxl = max(maxl, d[s])
	if a[i] == 0:
		maxl = i
	bad[i] = maxl + 1
	d[s] = i + 1
t = sum(bad)
ans = n * (n + 1) // 2 - t
print(ans)


n = int(input())
a = list(map(int, input().split()))
di = {}
di[0] = 0
ans = 0
total = 0
sub = -1
for i in range(n):
	total += a[i]
	if total in di:
		sub = max(sub, di[total])
	di[total] = i + 1
	ans += i - sub
print(ans)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	total = 0
	sd = {0: -1}
	s = 0
	mi = 0
	for i in range(n):
		s += a[i]
		if s in sd:
			mi = max(mi, sd[s] + 2)
		sd[s] = i
		total += i + 1 - mi
	print(total)

def main():
	solve()
main()


def problem(n, a):
	x = [0] + a[:]
	for i in range(n):
		x[i + 1] += x[i]
	(i, j, r, s) = (0, 0, 0, {0})
	while i < n:
		while j < n and x[j + 1] not in s:
			j += 1
			s.add(x[j])
		r += j - i
		s.remove(x[i])
		i += 1
	return r
print(problem(int(input()), list(map(int, input().split()))))


n = int(input())
l = input().split()
li = [int(i) for i in l]
sumi = [0]
sumnow = 0
for i in range(n):
	sumnow += li[i]
	sumi.append(sumnow)
hashi = dict()
lcpy = list(sumi)
count = 0
fromwhich = 0
for i in range(n + 1):
	if sumi[i] not in hashi:
		hashi[sumi[i]] = (1, i)
		count += len(hashi) - 1
	else:
		x = hashi[sumi[i]]
		y = x[1]
		for j in range(fromwhich, y + 1):
			del hashi[sumi[j]]
		hashi[sumi[i]] = (1, i)
		count += len(hashi) - 1
		fromwhich = y + 1
print(count)


import sys
input = lambda : sys.stdin.readline().strip()
ipnut = input
for i in range(1):
	n = int(ipnut())
	a = list(map(int, input().split()))
	s = {}
	s[0] = 1
	pref = [0]
	line = []
	ans = 0
	last = 0
	for i in range(n):
		pref.append(pref[-1] + a[i])
		if pref[-1] in s:
			last = max(last, s[pref[-1]])
		if abs(a[i]):
			ans += i + 1 - last
		s[pref[-1]] = i + 2
	print(ans)


import sys
input = sys.stdin.readline
from math import *
n = int(input())
a = [int(x) for x in input().split()]
d = {0: 0}
p = 0
c = (n ** 2 + n) // 2
prev = 0
for i in range(n):
	p += a[i]
	if p in d:
		c -= max(d[p] + 1 - prev, 0) * (n - i)
		prev = max(prev, d[p] + 1)
	if p in d:
		d[p] = max(d[p], i + 1)
	else:
		d[p] = i + 1
print(c)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
a = [int(i) for i in input().split(' ')]
ps = []
cur = 0
S = {0: 0}
combo = 0
ans = 0
m2 = -1
for (pos, i) in enumerate(a, 1):
	cur += i
	ans += pos
	tp = -1
	if cur in S:
		tp = S[cur]
	tp = max(tp, m2) + 1
	ans -= tp
	if cur in S:
		m2 = max(m2, S[cur])
	S[cur] = pos
print(ans)


n = int(input())
arr = list(map(int, input().strip().split()))[:n]
from collections import defaultdict
store = defaultdict(int)
sums = 0
ans = 0
mx = 0
store[0] = -1
for i in range(n):
	sums += arr[i]
	if store[sums] != 0:
		if sums == 0 and store[sums] == -1:
			mx = max(mx, 1)
		else:
			mx = max(mx, store[sums] + 1)
	store[sums] = i + 1
	ans += i + 1 - mx
print(ans)


n = int(input())
a = [0] + list(map(int, input().split()))
(hs, s, ans, hh) = ({0: 0}, 0, 0, -1)
for i in range(1, n + 1):
	s += a[i]
	if hs.__contains__(s):
		hh = max(hh, hs[s])
	ans += i - hh - 1
	hs[s] = i
print(ans)


n = int(input())
A = [int(i) for i in input().split()]
P = [0]
for i in range(n):
	P.append(P[-1] + A[i])
ans = 0
tmp = set([0])
left = 0
right = 0
while left < n:
	while right < n and P[right + 1] not in tmp:
		right += 1
		tmp.add(P[right])
	ans += right - left
	tmp.remove(P[left])
	left += 1
print(ans)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	prefix = [0 for _ in range(n + 1)]
	for i in range(1, n + 1, 1):
		prefix[i] = prefix[i - 1] + a[i - 1]
	cur_pref = dict()
	ans = 0
	begin = 0
	cur_pref[prefix[begin]] = 1
	end = 0
	while begin < n:
		while end < n and cur_pref.get(prefix[end + 1]) is None:
			end += 1
			cur_pref[prefix[end]] = 1
		ans += end - begin
		cur_pref.pop(prefix[begin])
		begin += 1
	print(ans)
solve()


n = int(input())
lis = list(map(int, input().split()))
ss = [0] * (n + 1)
ans = 0
for i in range(1, n + 1):
	ss[i] = ss[i - 1] + lis[i - 1]
d = {}
(ans, l) = (0, 0)
for i in range(n + 1):
	if ss[i] in d:
		d[ss[i]] += 1
	else:
		d[ss[i]] = 1
	while d[ss[i]] > 1:
		d[ss[l]] -= 1
		l += 1
	ans += i - l + 1
print(ans - n - 1)


import sys
import heapq

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def rinput():
	return map(int, input().split())

def rlinput():
	return list(map(int, input().split()))

def YES(flag):
	if flag:
		return 'YES'
	return 'NO'

def main():
	n = iinput()
	q = rlinput()
	(cl, p, res, con) = (dict(), [q[0] for i in range(n + 5)], 0, 0)
	cl[0] = 1
	for i in range(1, n):
		p[i] = p[i - 1] + q[i]
	for i in range(n):
		if p[i] in cl:
			con = max(con, cl[p[i]])
		cl[p[i]] = i + 2
		res += (i - con) * (q[i] != 0)
	print(res + n - q.count(0))
for i in range(1):
	main()


n = int(input())
d = n * (n + 1) // 2
s = 0
c = {0: 0}
k = -1
for (j, q) in enumerate(map(int, input().split())):
	s += q
	if s in c:
		i = c[s]
		if i > k:
			d -= (n - j) * (i - k)
			k = i
	c[s] = j + 1
print(d)


from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
pref = [0 for i in range(n + 1)]
for i in range(n):
	pref[i + 1] = pref[i] + a[i]
counter = defaultdict(int)
b = 0
ans = 0
for i in range(n + 1):
	counter[pref[i]] += 1
	while counter[pref[i]] > 1:
		counter[pref[b]] -= 1
		b += 1
	ans += i - b
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
a = [int(item) for item in input().split()]
cuma = [0]
for item in a:
	cuma.append(cuma[-1] + item)
dic = dict()
dic[cuma[0]] = 0
right_most = -1
ans = 0
for (i, item) in enumerate(cuma):
	if i == 0:
		continue
	if item in dic:
		ans += i - max(dic[item], right_most) - 1
		right_most = max(right_most, dic[item])
	else:
		ans += i - right_most - 1
	dic[item] = i
print(ans)


import sys, math
input = sys.stdin.readline

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input().strip()

def listStr():
	return list(input().strip())
import collections as col
import math, itertools

def solve():
	N = getInt()
	A = [0] + getInts()
	P = []
	curr_sum = 0
	for a in A:
		curr_sum += a
		P.append(curr_sum)
	right = 1
	ans = 0
	sums_seen = set()
	sums_seen.add(0)
	end = 1
	for j in range(1, N + 1):
		while end < N + 1 and P[end] not in sums_seen:
			sums_seen.add(P[end])
			end += 1
		ans += end - j
		sums_seen.remove(P[j - 1])
	return ans
print(solve())


N = int(input())
A = list(map(int, input().split()))
good_subarray = 0
prev_vals = {0: -1}
cum_sum = 0
left_boundary = -1
for (i, a) in enumerate(A):
	cum_sum += a
	if cum_sum == 0:
		left_boundary = prev_vals[0] + 1
	if cum_sum in prev_vals:
		if prev_vals[cum_sum] >= left_boundary:
			left_boundary = prev_vals[cum_sum] + 1
	good_subarray += i - left_boundary
	prev_vals[cum_sum] = i
print(good_subarray)


from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
a.append(0)
l = -1
t = 0
out = 0
s = defaultdict(lambda : float('-inf'))
s[0] = -1
for i in range(n + 1):
	t += a[i]
	if s[t] >= l:
		d1 = i - 1 - (l + 1) + 1
		d2 = i - 1 - (s[t] + 2) + 1
		out += d1 * (d1 + 1) // 2 - d2 * (d2 + 1) // 2
		l = s[t] + 1
		if a[i] == 0:
			l = i
	s[t] = i
print(out)


n = int(input())
arr = list(map(int, input().split()))
d = {}
arr = [0] + arr
s = 0
cnt = 0
m = 0
for i in range(n + 1):
	s += arr[i]
	if s in d:
		m = max(m, d[s] + 1)
	d[s] = i
	cnt += i - m
print(cnt)


a = int(input())
z = list(map(int, input().split()))
pre = [0]
for i in range(len(z)):
	pre.append(pre[-1] + z[i])
total = 0
mi = -1
from collections import defaultdict
al = defaultdict(list)
for i in range(len(pre)):
	if len(al[pre[i]]):
		x = al[pre[i]].pop()
		total += i - max(x, mi) - 1
		mi = max(x, mi)
		al[pre[i]].append(i)
	else:
		al[pre[i]].append(i)
		total += i - mi - 1
print(total)


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
ans = 0
st = {0}
cum_a = 0
idx_l = 0
cum_A = [0]
for (idx_r, a) in enumerate(A):
	cum_a += a
	cum_A.append(cum_a)
	while cum_a in st:
		st.remove(cum_A[idx_l])
		idx_l += 1
	st.add(cum_a)
	ans += idx_r - idx_l
print(ans + N)


n = int(input())
a = [0] + list(map(int, input().split()))
for i in range(1, n + 1):
	a[i] += a[i - 1]
mp = {0: 0}
(last, ans) = (0, 0)
for i in range(1, n + 1):
	if a[i] in mp and mp[a[i]] >= last:
		ans -= (mp[a[i]] - last + 1) * (n - i + 1)
		last = mp[a[i]] + 1
	mp[a[i]] = i
print(ans + n * (n + 1) // 2)


def eugene_and_an_array(n, a):
	table = {}
	total = 0
	table[0] = 0
	ans = 0
	posFrom = 0
	for posTo in range(0, n):
		if a[posTo] == 0:
			posFrom = posTo + 1
			continue
		ans += a[posTo]
		if ans in table:
			posFrom = max(table[ans] + 1, posFrom)
		total += posTo - posFrom + 1
		table[ans] = posTo + 1
	print(total)
n = int(input())
a = list(map(int, input().split()))
eugene_and_an_array(n, a)


n = int(input())
a = [0] + list(map(int, input().split()))
save = {0: 0}
mx = 0
sum = 0
ans = 0
for i in range(1, n + 1):
	sum += a[i]
	if save.get(sum, -1) >= mx:
		mx = save[sum] + 1
	save[sum] = i
	ans += i - mx
print(ans)


n = int(input())
ar = [int(x) for x in input().split()]
pre = [0] * (n + 1)
ans = 0
for i in range(n):
	pre[i + 1] = pre[i] + ar[i]
d = {}
i = 0
j = 0
d[0] = 1
while i < n:
	while j < n and pre[j + 1] not in d:
		j += 1
		d[pre[j]] = 1
	ans += j - i
	d.pop(pre[i])
	i += 1
print(ans)


n = int(input())
a = list(map(int, input().split()))
ans = 0
dp = [i for i in range(n)]
pre = [0 for i in range(n)]
r = {}
if a[0] != 0:
	ans += 1
r[a[0]] = 0
pre[0] = a[0]
r[0] = -1
for i in range(1, n):
	pre[i] = pre[i - 1] + a[i]
	if a[i] != 0 and a[i - 1] != 0:
		t = dp[i - 1]
		k = r.get(pre[i], -2) + 1
		if pre[i] - (pre[t - 1] if t - 1 >= 0 else 0) != 0 and k < t:
			ans += i - t + 1
			dp[i] = t
		elif k >= t:
			t = k + 1
			ans += i - t + 1
			dp[i] = t
		elif pre[i] - (pre[t - 1] if t - 1 >= 0 else 0) == 0:
			t += 1
			ans += i - t + 1
			dp[i] = t
	elif a[i] != 0:
		ans += 1
	r[pre[i]] = i
print(ans)


def solve(a, size):
	hash_map = {0: 0}
	track_sum = 0
	bad_comb = 0
	total = 0
	for i in range(1, size + 1):
		track_sum += a[i - 1]
		if track_sum in hash_map:
			bad_comb = max(bad_comb, hash_map[track_sum] + 1)
		elif track_sum == 0:
			bad_comb = max(bad_comb, 1)
		hash_map[track_sum] = i
		total += i - bad_comb
	return total
size = int(input())
a = list(map(int, input().split()))
print(solve(a, size))


import sys

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def N():
	return int(input())
from collections import defaultdict
n = N()
arr = list(RL())
sm = [0]
res = 0
for i in arr:
	sm.append(sm[-1] + i)
l = 0
dic = defaultdict(int)
for i in range(1, n + 1):
	if sm[i] == 0 or sm[i] in dic:
		l = max(l, dic[sm[i]] + 1)
	res += i - l
	dic[sm[i]] = i
print(res)


from collections import defaultdict
R = lambda : map(int, input().split())
d = defaultdict(list)
n = int(input())
a = list(R())
s = 0
d[0] = [-1]
for i in range(n):
	s += a[i]
	d[s].append(i)
blocks = [n] * len(a)
for ar in d.values():
	for i in range(1, len(ar)):
		blocks[ar[i - 1] + 1] = ar[i]
for i in range(n - 2, -1, -1):
	if blocks[i] > blocks[i + 1]:
		blocks[i] = blocks[i + 1]
ans = [blocks[i] - i for i in range(len(blocks))]
print(sum(ans))


n = int(input())
a = list(map(int, input().split()))
t = n * (n + 1) // 2
s = 0
d = {}
b = []
d[0] = -1
for i in range(n):
	s += a[i]
	try:
		b.append([d[s] + 1, i])
		d[s] = i
	except:
		d[s] = i
if len(b) == 0:
	print(t)
	exit()
pre = b[0]
(u, v) = pre
ans = (u + 1) * (n - v)
mx = u
for p in b[1:]:
	(i, j) = p
	(x, y) = pre
	if x > mx:
		mx = x
	if i - x > 0:
		ans += (i - mx) * (n - j)
	pre = p
print(t - ans)


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
n = int(input())
a = list(map(int, input().split()))
dic = {}
dic[0] = -1
nsum = 0
ans = 0
ll = -2
for i in range(n):
	nsum += a[i]
	if nsum in dic:
		ll = max(dic[nsum], ll)
	ans += i - ll - 1
	dic[nsum] = i
print(ans)


import sys
lines = sys.stdin.readlines()
n = int(lines[0].strip())
nums = list(map(int, lines[1].strip().split(' ')))
seen = {0: -1}
tmpSum = 0
prev = -1
res = 0
for i in range(n):
	tmpSum += nums[i]
	if tmpSum not in seen or seen[tmpSum] < prev:
		seen[tmpSum] = i
		res += i - prev
	else:
		prev = seen[tmpSum] + 1
		seen[tmpSum] = i
		res += i - prev
print(res)


import sys, os.path
from collections import *
from copy import *
import math
mod = 10 ** 9 + 7
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
n = int(input())
a = list(map(int, input().split()))
curr = 0
d = {}
d[0] = -1
maxind = 0
ans = 0
for i in range(n):
	curr += a[i]
	if curr in d:
		maxind = max(maxind, d[curr] + 2)
	d[curr] = i
	ans += i - maxind + 1
print(ans)


N = int(input())
D = {0: -1}
A = [int(a) for a in input().split()]
m = -1
s = 0
ans = 0
for (i, a) in enumerate(A):
	if a == 0:
		m = i
		continue
	s += a
	if s not in D:
		D[s] = i
		ans += i - m
	else:
		m = max(m, D[s] + 1)
		ans += i - m
		D[s] = i
print(ans)


from math import *
from bisect import bisect_left, bisect_right
from sys import stdin, stdout
from collections import Counter
input = lambda : stdin.readline().strip()
print = stdout.write
n = int(input())
ls = list(map(int, input().split()))
d = {}
s = 0
prev = 0
ans = 0
flag = 0
for i in range(n):
	s += ls[i]
	if ls[i] == 0:
		prev = i + 1
		s = 0
	else:
		try:
			if d[s] >= prev:
				prev = d[s] + 2
				ans += i - prev + 1
				s = -ls[d[s] + 1]
				flag = 1
		except:
			pass
		if not flag:
			if s == 0:
				ans += i - prev
				s -= ls[prev]
				prev += 1
			else:
				ans += i - prev + 1
	d[s] = i
	flag = 0
print(str(ans) + '\n')


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def findSubArrays(arr, n):
	hashMap = {}
	hashMap[0] = -1
	s = 0
	lis = []
	sum1 = 0
	for i in range(n):
		sum1 += arr[i]
		if sum1 in hashMap.keys():
			if s != 0 and hashMap[sum1] >= lis[-1][0]:
				lis.append([hashMap[sum1] + 1, i])
				s += 1
				hashMap[sum1] = i
			elif s != 0 and hashMap[sum1] < lis[-1][0]:
				hashMap[sum1] = i
			elif s == 0:
				lis.append([hashMap[sum1] + 1, i])
				hashMap[sum1] = i
				s += 1
		else:
			hashMap[sum1] = i
	return lis
n = int(input())
arr = list(map(int, input().split()))
lis = findSubArrays(arr, n)
a = len(lis)
if a == 0:
	print(n * (n + 1) // 2)
else:
	j = 0
	num = [0] * a
	array = []
	for i in range(n):
		if j < a:
			if num[j] == 0:
				array.append(lis[j][1] - i)
				num[j] = 1
			else:
				array.append(0)
			if lis[j][0] == i:
				j += 1
		else:
			array.append(n - i)
			for l in range(n - i - 1):
				array.append(0)
			break
	ans = 0
	b = len(array)
	for i in range(b):
		if array[i] > 0:
			temp = array[i] - 1
			ans += array[i] * (array[i] + 1) // 2
			for j in range(i + 1, i + array[i]):
				if array[i] > 0:
					temp1 = min(temp, array[j])
					ans -= temp1 * (temp1 + 1) // 2
				temp -= 1
	print(ans)


import sys
import io, os

def main():
	n = int(input())
	a = [int(i) for i in input().split()]
	(track, pref) = (dict(), 0)
	track[0] = 0
	counter = 0
	ans = 0
	for i in range(len(a)):
		pref += a[i]
		if pref in track:
			ans = ans + min(i + 1 - counter, i - track[pref])
			if counter < track[pref] + 1:
				counter = track[pref] + 1
			track[pref] = i + 1
		else:
			track[pref] = i + 1
			ans += i + 1 - counter
	print(ans)
main()


from collections import defaultdict
n = int(input())
l = list(map(int, input().split()))
sumi = 0
d = defaultdict(int)
for i in range(n):
	sumi += l[i]
	d[sumi] = -1
sumi = 0
index = -1
count = 0
for i in range(n):
	sumi += l[i]
	if l[i] == 0:
		index = i
		count += i - index
		d[sumi] = i
	elif sumi == 0:
		index = max(d[sumi] + 1, index)
		count += i - index
		d[sumi] = i
	elif d[sumi] != -1:
		index = max(d[sumi] + 1, index)
		count += i - index
		d[sumi] = i
	else:
		d[sumi] = i
		count += i - index
print(count)


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
tmp = 0
dic = {0: 1}
ans = 0
least = 0
for (i, a) in enumerate(A):
	tmp += a
	if a == 0:
		least = i + 1
		continue
	elif tmp in dic:
		least = max(least, dic[tmp])
	ans += i + 1 - least
	dic[tmp] = i + 2
print(ans)


import sys
import itertools
import collections
input = sys.stdin.readline

def main():
	N = int(input())
	A = [int(x) for x in input().split()]
	AA = [0] + list(itertools.accumulate(A)) + [10 ** 9 + 7]
	ans = 0
	next = 1
	c = collections.Counter()
	c[0] = 1
	for i in range(N + 1):
		while next <= N and c[AA[next]] != 1:
			c[AA[next]] += 1
			next += 1
		ans += next - i - 1
		c[AA[i]] -= 1
	print(ans)
main()


from itertools import accumulate

def lengthOfLongestSubstring(A):
	ans = 0
	lastSeen = {A[0]: 0}
	l = 0
	for i in range(1, len(A)):
		if A[i] not in lastSeen:
			ans += max(0, i - l)
		else:
			l = max(l, lastSeen[A[i]] + 1)
			ans += max(0, i - l)
		lastSeen[A[i]] = i
	return ans
n = int(input())
a = [int(x) for x in input().split()]
cum = list(accumulate(a))
ans = lengthOfLongestSubstring(cum)
seen = set()
for i in range(len(cum)):
	if cum[i] == 0:
		break
	elif cum[i] not in seen:
		ans += cum[i] != 0
	else:
		break
	seen.add(cum[i])
print(ans)


from sys import stdin, stdout
input = stdin.readline

def A():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		print('W' + 'B' * (m - 1))
		for i in range(1, n):
			print('B' * m)

def B():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		b = list(map(int, input().split()))
		foundNeg = False
		foundPos = False
		succ = True
		for i in range(n):
			if a[i] > b[i]:
				if not foundNeg:
					succ = False
					break
			elif a[i] < b[i]:
				if not foundPos:
					succ = False
					break
			if a[i] > 0:
				foundPos = True
			elif a[i] < 0:
				foundNeg = True
		if succ:
			print('YES')
		else:
			print('NO')
	return

def C():
	from collections import defaultdict
	n = int(input())
	a = list(map(int, input().split()))
	d = defaultdict()
	d[0] = -1
	b = [a[0]] * n
	for i in range(1, n):
		b[i] = b[i - 1] + a[i]
	front = -1
	tot = 0
	for j in range(n):
		x = d.get(b[j], -2)
		if x >= front:
			front = x + 1
		tot += j - front
		d[b[j]] = j
	print(tot)

def D():
	return
C()


from collections import Counter
n = int(input())
a = [int(x) for x in input().split()]
result = 0
prefix = [0]
for val in a:
	prefix.append(prefix[-1] + val)
seen = set([0])
r = 0
for l in range(n):
	while r < n and prefix[r + 1] not in seen:
		seen.add(prefix[r + 1])
		r += 1
	result += r - l
	seen.remove(prefix[l])
print(result)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, sys
from sys import stdin, stdout

def modinv(n, p):
	return pow(n, p - 2, p)

def nc():
	return map(int, ns().split())

def narr():
	return list(map(int, ns().split()))

def ns():
	return input()

def ni():
	return int(input())
n = ni()
a = narr()
closest_beg = [-1] * n
last_seen = {}
last_seen_zero = -1
ss = 0
for i in range(0, n):
	if a[i] == 0:
		last_seen_zero = i
	ss += a[i]
	if ss in last_seen:
		closest_beg[i] = last_seen[ss] + 1
	elif ss == 0:
		closest_beg[i] = 0
	closest_beg[i] = max(last_seen_zero, closest_beg[i])
	if i > 0:
		closest_beg[i] = max(closest_beg[i - 1], closest_beg[i])
	last_seen[ss] = i
ans = 0
for i in range(n):
	if closest_beg[i] == -1:
		ans += i + 1
	else:
		ans += i - closest_beg[i]
print(ans)


import sys
n = int(input())
l = list(map(int, input().split()))
p = [0] * (n + 1)
for i in range(1, n + 1):
	p[i] = p[i - 1] + l[i - 1]
secik = set()
pr = 0
le = 0
p += [p[-1]]
n += 1
odp = 0
while True:
	if le == n:
		print(odp)
		break
	if len(secik) == pr - le:
		secik.add(p[pr])
		pr += 1
	else:
		odp += pr - le - 2
		if p[le] != p[pr - 1]:
			secik.remove(p[le])
		le += 1


n = int(input())
kk = dict()
s = [int(x) for x in input().split()]
L = [0]
kk[0] = -1
rngs = [-1] * (n + 10)
rnge = [-1] * (n + 10)
c = 1
for i in range(0, len(s)):
	L.append(L[-1] + s[i])
	if kk.get(L[-1]) != None:
		rngs[kk[L[-1]] + 1] = c
		rnge[i] = c
		c += 1
	kk[L[-1]] = i
ans = 0
ptr = 0
pos = dict()
lst = 0
diff = 0
while ptr < len(s):
	if rngs[ptr] != -1:
		pos[rngs[ptr]] = ptr
	if rnge[ptr] != -1:
		if pos.get(rnge[ptr]) != None:
			tot = ptr - lst
			ans += tot * (tot + 1) // 2
			tot2 = ptr - pos[rnge[ptr]] - 1
			ans -= tot2 * (tot2 + 1) // 2
			ptr = pos[rnge[ptr]]
			lst = ptr + 1
			pos.clear()
	ptr += 1
tot = ptr - lst
ans += tot * (tot + 1) // 2
print(ans)


from itertools import accumulate
n = int(input())
a = [int(x) for x in input().split()]
sums = [0] + list(accumulate(a))
s = {0}
(i, j) = (0, 0)
ans = 0
while i < n:
	while j < n and sums[j + 1] not in s:
		s.add(sums[j + 1])
		j += 1
	ans += j - i
	s.remove(sums[i])
	i += 1
print(ans)


import sys
from collections import defaultdict as dd
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
res = 0
cs = [0] * (N + 1)
for i in range(N):
	cs[i + 1] = cs[i] + a[i]
d = dd(list)
for i in range(N + 1):
	d[cs[i]].append(i)
table = [0] * N
for i in range(N):
	j = br(d[cs[i]], i)
	r = N
	if j < len(d[cs[i]]):
		r = d[cs[i]][j] - 1
	table[i] = r
for i in range(N - 1, 0, -1):
	table[i - 1] = min(table[i - 1], table[i])
for i in range(N):
	res += table[i] - i
print(res)


n = int(input())
a = [int(i) for i in input().split()]
prefix_sum = [0]
for i in range(n):
	prefix_sum.append(prefix_sum[-1] + a[i])
ans = 0
pos = 0
s = set()
s.add(prefix_sum[0])
i = 0
j = 0
while i < n:
	while j < n and prefix_sum[j + 1] not in s:
		s.add(prefix_sum[j + 1])
		j += 1
	ans += j - i
	if prefix_sum[i] in s:
		s.remove(prefix_sum[i])
	i += 1
print(ans)


n = int(input())
arr = list(map(int, input().split()))
dic = {0: -1}
temp = 0
res = 0
prev = 0
for i in range(n):
	temp += arr[i]
	if temp in dic:
		prev = max(prev, dic[temp] + 2)
	res += i - prev + 1
	dic[temp] = i
print(res)


def main():
	n = int(input())
	arr = list(map(int, input().split()))
	begin = 0
	dp = [0]
	for i in range(1, n + 1):
		dp.append(dp[i - 1] + arr[i - 1])
	end = 0
	d = {0: 1}
	ans = 0
	while begin < n:
		while end < n and (d.get(dp[end + 1]) == None or d[dp[end + 1]] == 0):
			end += 1
			d[dp[end]] = 1
		ans += end - begin
		d[dp[begin]] = 0
		begin += 1
	print(ans)
	return
main()


from collections import OrderedDict
N = int(input())
A = list(map(int, input().split()))
S = [0]
for a in A:
	S.append(S[-1] + a)
d = OrderedDict()
res = []
for (i, s) in enumerate(S):
	if s not in d:
		d[s] = i
	else:
		t = d[s]
		to_remove = []
		for (u, v) in list(d.items()):
			if v <= t:
				res.append((v, i - 1))
				to_remove.append(u)
			else:
				break
		for x in to_remove:
			del d[x]
		d[s] = i
for (i, j) in d.items():
	res.append((j, N))
value = 0
for (i, j) in res:
	value += j - i
print(value)


import os
import sys
from io import BytesIO, IOBase
import math
from queue import Queue
import collections
import itertools
import bisect
import heapq
import random

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(int(n))
	return l

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def maxPrimeFactors(n):
	maxPrime = -1
	while n % 2 == 0:
		maxPrime = 2
		n >>= 1
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			maxPrime = i
			n = n / i
	if n > 2:
		maxPrime = n
	return int(maxPrime)

def countcon(s, i):
	c = 0
	ch = s[i]
	for i in range(i, len(s)):
		if s[i] == ch:
			c += 1
		else:
			break
	return c

def lis(arr):
	n = len(arr)
	lis = [1] * n
	for i in range(1, n):
		for j in range(0, i):
			if arr[i] > arr[j] and lis[i] < lis[j] + 1:
				lis[i] = lis[j] + 1
	maximum = 0
	for i in range(n):
		maximum = max(maximum, lis[i])
	return maximum

def isSubSequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def maxfac(n):
	root = int(n ** 0.5)
	for i in range(2, root + 1):
		if n % i == 0:
			return n // i
	return n

def p2(n):
	c = 0
	while n % 2 == 0:
		n //= 2
		c += 1
	return c

def seive(n):
	primes = [True] * (n + 1)
	primes[1] = primes[0] = False
	i = 2
	while i * i <= n:
		if primes[i] == True:
			for j in range(i * i, n + 1, i):
				primes[j] = False
		i += 1
	pr = []
	for i in range(0, n + 1):
		if primes[i]:
			pr.append(i)
	return pr

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def denofactinverse(n, m):
	fac = 1
	for i in range(1, n + 1):
		fac = fac * i % m
	return pow(fac, m - 2, m)

def numofact(n, m):
	fac = 1
	for i in range(1, n + 1):
		fac = fac * i % m
	return fac

def sod(n):
	s = 0
	while n > 0:
		s += n % 10
		n //= 10
	return s
n = int(input())
l = list(map(int, input().split()))
d = {0: -1}
cs = 0
ans = 0
prev = -1
for i in range(0, n):
	cs += l[i]
	if cs in d:
		prev = d[cs] + 1
		d = {0: i - 1, l[i]: i}
		cs = l[i]
	d[cs] = i
	ans += i - prev
print(ans)


import sys
n = int(sys.stdin.readline().strip())
l = [int(j) for j in sys.stdin.readline().split()]
pre = [0] * (n + 1)
last = 0
for i in range(1, n + 1):
	pre[i] = pre[i - 1] + l[i - 1]
last = 0
ans = 0
idx = dict()
idx[0] = 0
for i in range(1, n + 1):
	if pre[i] in idx:
		last = max(last, idx[pre[i]] + 1)
	ans += max(0, i - last)
	idx[pre[i]] = i
print(ans)


n = int(input())
lis = list(map(int, input().split()))
pre = [0] * (n + 1)
for i in range(1, n + 1):
	pre[i] = pre[i - 1] + lis[i - 1]
d = {}
ans = l = 0
for i in range(n + 1):
	if pre[i] not in d:
		d[pre[i]] = i
	else:
		l = max(l, d[pre[i]] + 1)
		d[pre[i]] = i
	ans += i - l
print(ans)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
mod2 = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

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

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def IF(c, t, f):
	return t if c else f

def YES(c):
	return IF(c, 'YES', 'NO')

def Yes(c):
	return IF(c, 'Yes', 'No')

def main():
	t = 1
	rr = []
	for _ in range(t):
		n = I()
		a = LI()

		def f(a):
			c = {}
			c[0] = -1
			m = -1
			t = 0
			r = 0
			for (i, b) in enumerate(a):
				t += b
				if t in c:
					u = c[t]
					if m <= u:
						m = u + 1
				r += i - m
				c[t] = i
			return r
		r = 0
		i = 0
		for (j, c) in enumerate(a):
			if c == 0:
				if i < j:
					r += f(a[i:j])
				i = j + 1
		if i < n:
			r += f(a[i:])
		rr.append(r)
	return JA(rr, '\n')
print(main())


import copy
import sys
input = lambda : sys.stdin.readline().rstrip()
n = int(input())
A = list(map(int, input().split()))
S = {0: 0}
s = 0
res = 0
accum = 0
for i in range(len(A)):
	s += A[i]
	if s in S:
		accum = min(accum + 1, i - S[s])
	else:
		accum += 1
	S[s] = i + 1
	res += accum
print(res)


from collections import defaultdict

def solve(n, a):
	d_pos = defaultdict(lambda : -1)
	last_zero_pos = -1
	current_sum = 0
	good_count = 0
	for i in range(n):
		d_pos[current_sum] = i
		current_sum += a[i]
		if current_sum in d_pos:
			idx = max(d_pos[current_sum], last_zero_pos)
			last_zero_pos = idx
		else:
			idx = last_zero_pos
		if a[i] == 0:
			last_zero_pos = i
		good_count += i - idx
		d_pos[current_sum] = i + 1
	return good_count
n = int(input())
a = list(map(int, input().split()))
r = solve(n, a)
print(r)


def solve(arr):
	prefix = {}
	i = count = s = 0
	maxL = -1
	for i in range(len(arr)):
		s += arr[i]
		if s in prefix:
			last = prefix[s]
			maxL = max(maxL, last + 1)
		elif s == 0:
			maxL = 0
		prefix[s] = i
		count += i - maxL
	return count
x = input()
arr = list(map(int, input().split()))
print(solve(arr))


n = int(input())
arr = list(map(int, input().split(' ')))
prefix = [0]
prefix_set = set()
ans = 0
for i in range(n):
	prefix.append(arr[i] + prefix[i])
i = 0
j = 0
prefix_set.add(0)
while i < n:
	while j < n and (not prefix[j + 1] in prefix_set):
		j = j + 1
		prefix_set.add(prefix[j])
	ans = ans + j - i
	prefix_set.remove(prefix[i])
	i = i + 1
print(ans)


t = int(input())
b = list(map(int, input().split()))
s = 0
p = 0
q = 0
c = dict()
for j in range(t):
	s += b[j]
	if s == 0 and q == 0:
		p += j + 1 - 1
		c[0] = j
		q = 1
	else:
		if s in c.keys():
			k = c[s]
			q = max(q, k + 2)
		c[s] = j
		p += j + 1 - q
print(p)


n = int(input())
prefix = [0] * (n + 1)
for (i, x) in enumerate(input().split()):
	x = int(x)
	prefix[i + 1] = prefix[i] + x
begin = 0
end = 0
ans = 0
s = {0}
while begin < n:
	while end < n and prefix[end + 1] not in s:
		end += 1
		s.add(prefix[end])
	ans += end - begin
	s.remove(prefix[begin])
	begin += 1
print(ans)


from math import *
n = int(input())
ar = list(map(int, input().split()))
p = [0]
for i in range(n):
	p.append(ar[i] + p[-1])
d = {}
m = 0
ans = 0
for i in range(n + 1):
	if p[i] in d:
		m = max(m, d[p[i]] + 1)
	ans += i - m
	d[p[i]] = i
print(ans)


import sys
readline = sys.stdin.readline
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : map(int, readline().split())
nl = lambda : list(map(int, readline().split()))

def solve():
	n = ni()
	a = nl()
	d = dict()
	d[0] = -1
	ans = c = 0
	v = -2
	for i in range(n):
		c += a[i]
		if c in d:
			v = max(v, d.get(c, -1))
		ans += i - v - 1
		d[c] = i
	print(ans)
	return
solve()


n = int(input())
a = {0: 0}
b = -1
s = s1 = 0
for (i, j) in enumerate(map(int, input().split())):
	s += j
	if s in a:
		b = max(b, a[s])
	s1 += i - b
	a[s] = i + 1
print(s1)


n = int(input())
a = list(map(int, input().split()))
h = {0: -1}
s = 0
ans = 0
t = -1
for i in range(n):
	if a[i] != 0:
		s += a[i]
		if s in h and h[s] >= t:
			ans += i - h[s] - 1
			t = h[s] + 1
		else:
			ans += i - t
			h[s] = i
	if a[i] == 0:
		t = i
		h = {0: i}
	else:
		h[s] = i
print(ans)


n = int(input())
a = list(map(int, input().split()))
s = 0
mi = -1
c = {0: -1}
su = 0
for i in range(n):
	if a[i] == 0:
		c = {0: i}
		su = 0
		mi = i
	else:
		su += a[i]
		if su in c:
			mi = max(mi, c[su] + 1)
		c[su] = i
		s += i - mi
print(s)


from decimal import *
from math import floor, ceil
from collections import defaultdict

def read_ints():
	return list(map(int, input().split(' ')))

def solve():
	n = int(input())
	a = read_ints()
	prefs = [0] * (n + 1)
	for i in range(1, n + 1):
		prefs[i] = a[i - 1] + prefs[i - 1]
	last_seen = defaultdict(lambda : float('-inf'))
	last_seen[0] = 0
	best_left = [0] * (n + 1)
	answer = 0
	for i in range(1, n + 1):
		curr_right = i - 1
		best_left[i] = max(best_left[i - 1], last_seen[prefs[i]] + 1)
		last_seen[prefs[i]] = i
		answer += curr_right - best_left[i] + 1
	print(answer)

def main():
	solve()
main()


from collections import Counter
n = int(input())
a = [int(x) for x in input().split()]
p = [0] + a[:]
for i in range(n):
	p[i + 1] += p[i]
z = Counter()
z[0] += 1
i = 0
j = 0
an = 0
while i < n:
	while j < n and (not z[p[j + 1]]):
		j += 1
		z[p[j]] += 1
	an += j - i
	z[p[i]] -= 1
	i += 1
print(an)


n = int(input())
l = list(map(int, input().split()))
ans = 0
d = {0: -1}
pref = 0
ind = -1
for i in range(n):
	pref += l[i]
	if pref in d:
		ind = max(ind, d[pref] + 1)
	d[pref] = i
	ans += i - ind
print(ans)


from sys import stdin, stdout
for _ in range(1):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	ans = sm = 0
	s = {0: -1}
	last = 0
	for i in range(n):
		sm += a[i]
		if sm in s:
			last = max(s[sm] + 2, last)
		ans += i - last + 1
		s[sm] = i
	print(ans)


import bisect
import os
import io
from collections import Counter
import bisect
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce, cmp_to_key
from collections import deque
import threading
from itertools import combinations

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def tinput():
	return input().split()

def rinput():
	return map(int, tinput())

def rlinput():
	return list(rinput())

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))
n = iinput()
a = rlinput()
pref = [0] * (n + 1)
for i in range(n):
	pref[i + 1] = pref[i] + a[i]
d = defaultdict(int)
ans = 0
start = 0
for i in range(n + 1):
	d[pref[i]] += 1
	while d[pref[i]] > 1:
		d[pref[start]] -= 1
		start += 1
	ans += i - start
print(ans)


n = int(input())
A = list(map(int, input().split()))
rs = []
cur = 0
for a in A:
	cur += a
	rs.append(cur)
last_seen = {}
max_r = n
out = 0
for i in range(n - 1, -1, -1):
	s = rs[i]
	max_r = min(max_r, last_seen.get(s, n))
	out += max_r - (i + 1)
	last_seen[s] = i
max_r = min(max_r, last_seen.get(0, n))
out += max_r
print(out)


n = int(input())
arr = list(map(int, input().strip().split()))
arr = arr
(h, hh, s, ans) = ({0: 0}, -1, 0, 0)
for i in range(n):
	s += arr[i]
	if s in h:
		hh = max(hh, h[s])
	h[s] = i + 1
	ans += i - hh
print(ans)


def good_array(arr, n):
	hash_sum = dict()
	curr_sum = ans = 0
	start = 0
	for i in range(0, n + 1):
		curr_sum += arr[i]
		if curr_sum in hash_sum:
			start = max(start, hash_sum[curr_sum] + 1)
		ans += i - start
		hash_sum[curr_sum] = i
	return ans
n = int(input())
arr = [0] + list(map(int, input().split()))
print(good_array(arr, n))


import sys
from functools import lru_cache
from heapq import merge, heapify, heappop, heappush
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf
from collections import defaultdict as dd, deque, Counter as c
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(var):
	sys.stdout.write(str(var))

def outln(var):
	sys.stdout.write(str(var) + '\n')

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
n = int(data())
arr = l()
arr.insert(0, 0)
s = 0
m = 0
answer = 0
dp = dd(int)
dp[0] = 1
for i in range(1, n + 1):
	s += arr[i]
	if s in dp.keys():
		m = max(m, dp[s])
	dp[s] = i + 1
	answer += i - m
out(answer)


n = int(input())
nums = list(map(int, input().split()))
prefixSum = []
for i in range(n):
	if i == 0:
		prefixSum.append(nums[0])
	else:
		prefixSum.append(prefixSum[i - 1] + nums[i])
next_val = {}
ans = 0
r_max = n - 1
for i in range(n - 1, -1, -1):
	next_val[prefixSum[i]] = i
	if i == 0:
		prefixSum[i - 1] = 0
	if prefixSum[i - 1] in next_val:
		r_max = min(next_val[prefixSum[i - 1]] - 1, r_max)
	ans += r_max - i + 1
print(ans)


import sys
input = sys.stdin.readline
n = int(input()) + 1
a = [0] + list(map(int, input().split()))

def init_min(init_min_val):
	for i in range(n):
		seg_min[i + num_min - 1] = init_min_val[i]
	for i in range(num_min - 2, -1, -1):
		seg_min[i] = min(seg_min[2 * i + 1], seg_min[2 * i + 2])

def update_min(k, x):
	k += num_min - 1
	seg_min[k] = x
	while k:
		k = (k - 1) // 2
		seg_min[k] = min(seg_min[k * 2 + 1], seg_min[k * 2 + 2])

def query_min(p, q):
	if q <= p:
		return ide_ele_min
	p += num_min - 1
	q += num_min - 2
	res = ide_ele_min
	while q - p > 1:
		if p & 1 == 0:
			res = min(res, seg_min[p])
		if q & 1 == 1:
			res = min(res, seg_min[q])
			q -= 1
		p = p // 2
		q = (q - 1) // 2
	if p == q:
		res = min(res, seg_min[p])
	else:
		res = min(min(res, seg_min[p]), seg_min[q])
	return res
ide_ele_min = n
num_min = 2 ** (n - 1).bit_length()
seg_min = [ide_ele_min] * 2 * num_min
d = dict()
b = [0] * n
for i in range(n):
	b[i] = b[i - 1] + a[i]
for i in range(n):
	if a[i] == 0:
		update_min(i, i)
		d[b[i]] = i
	elif b[i] in d:
		update_min(d[b[i]] + 1, i)
	d[b[i]] = i
res = 0
for i in range(n):
	res += query_min(i, n) - i
print(res)


n = int(input())
l = list(map(int, input().split()))
prefix_sum = [0]
for i in range(n):
	prefix_sum.append(prefix_sum[-1] + l[i])
start = end = 0
ans = 0
s = set()
s.add(0)
while start < n:
	while end < n and prefix_sum[end + 1] not in s:
		end += 1
		s.add(prefix_sum[end])
	ans += end - start
	s.remove(prefix_sum[start])
	start += 1
print(ans)


import bisect
n = int(input())
l = [int(x) for x in input().split()]
ind = {0: -1}
s = 0
c = 0
j = -1
for i in range(n):
	s += l[i]
	if s not in ind:
		ind[s] = i
		c += i - j
	elif s in ind:
		j = max(j, ind[s] + 1)
		c += i - j
		ind[s] = i
print(c)


n = int(input())
a = list((int(i) for i in input().split()))
p = [0] * (n + 1)
for i in range(0, n):
	p[i + 1] += p[i] + a[i]
ok = dict()
(ans, l) = (0, 0)
for i in range(n + 1):
	if p[i] in ok:
		ok[p[i]] += 1
	else:
		ok[p[i]] = 1
	while ok[p[i]] > 1:
		ok[p[l]] -= 1
		l += 1
	ans += i - l + 1
print(ans - n - 1)


import math, sys
from collections import Counter

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

def ls():
	return list(map(int, list(input())))

def la():
	return list(input())

def i():
	return int(input())

def isPrime(n):
	i = 2
	if n == 1:
		return False
	while i <= int(math.sqrt(n)):
		if n % i == 0:
			return False
		i = i + 1
	return True

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
n = i()
a = li()
cursum = 0
d = {}
d[0] = 1
ans = 0
m = 0
for i in range(n):
	cursum += a[i]
	if cursum in d:
		m = max(d[cursum], m)
	d[cursum] = i + 2
	ans += i + 1 - m
print(ans)


n = int(input())
l = list(map(int, input().split()))
b = [0]
z = 0
x = -1
a = {}
cnt = 0
for i in range(n):
	z += l[i]
	b.append(z)
for i in range(len(b)):
	if b[i] in a:
		x = max(x, a[b[i]])
	cnt += i - x - 1
	a[b[i]] = i
print(cnt)


n = int(input())
arr = list(map(int, input().split()))
pref = [0]
for i in arr:
	pref.append(pref[-1] + i)
left = {}
ans = 0
maxleft = 0
for (num, element) in enumerate(pref):
	plus = num
	if element in left:
		maxleft = max(maxleft, left[element] + 1)
	plus = num - maxleft
	left[element] = num
	ans += plus
print(ans)


n = int(input())
arr = list(map(int, input().split()))
notneeded = dict()
notneeded[0] = -1
ans = sum = mx = 0
for (i, elem) in enumerate(arr):
	sum += elem
	if sum in notneeded:
		mx = max(mx, notneeded[sum] + 2)
	ans += mx
	notneeded[sum] = i
z = len(arr)
print(int(z * (z + 1) // 2) - ans)


n = int(input())
a = list(map(int, input().split()))
mp = dict()
mp[0] = -1
pre = 0
mx = -1
ans = 0
for i in range(n):
	pre += a[i]
	ok = mp.get(pre, 'Huh')
	if ok == 'Huh':
		ans += i - mx
		mp[pre] = i
	else:
		if mx < ok + 1:
			mx = ok + 1
		ans += i - mx
	mp[pre] = i
print(ans)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	psum = [0] + a
	for i in range(n):
		psum[i + 1] += psum[i]
	ans = 0
	dic = {0: 0}
	rightmost = 0
	for i in range(1, n + 1):
		if psum[i] in dic:
			rightmost = max(rightmost, dic[psum[i]] + 1)
		ans += i - rightmost
		dic[psum[i]] = i
	print(ans)
solve()


import collections as cl
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b = [0]
for i in range(n):
	b.append(b[-1] + a[i])
c = {b[n]: n}
d = [n] * (n + 1)
ans = 0
for i in reversed(range(n)):
	if b[i] in c:
		d[i] = c[b[i]] - 1
	c[b[i]] = i
	d[i] = min(d[i], d[i + 1])
	ans += d[i] - i
print(ans)


n = int(input())
sp = list(map(int, input().split()))
pref = [0] * (n + 1)
for i in range(n):
	pref[1 + i] = pref[i] + sp[i]
i = 1
while i < n + 1:
	if pref[i] != 0:
		break
	i += 1
if i == n + 1:
	print(0)
	exit()
d = dict()
d[pref[i]] = i
ans = 1
d[0] = 0
proshn = i - 1
for j in range(i + 1, n + 1):
	if pref[j] == pref[j - 1]:
		proshn = j
		continue
	if pref[j] in d:
		ans += j - max(proshn, d[pref[j]] + 1)
		proshn = max(proshn, d[pref[j]] + 1)
		d[pref[j]] = j
	else:
		d[pref[j]] = j
		ans += j - max(i - 1, proshn)
print(ans)


from distutils.sysconfig import customize_compiler

def Sol(n, a_in):
	a = [0] + a_in
	answ = 0
	cur_ac_sums = {0}
	ac_sums = [0 for i in range(n + 1)]
	cur_sum = 0
	begin_ind = 1
	prev_end_ind = 0
	pivot_sum_ind = 0
	for i in range(1, n + 1):
		cur_sum += a[i]
		ac_sums[i] = cur_sum
		if cur_sum in cur_ac_sums:
			end_ind = i
			good_l = end_ind - begin_ind
			intersection_l = prev_end_ind - begin_ind
			answ += good_l * (good_l + 1) // 2 - intersection_l * (intersection_l + 1) // 2
			prev_end_ind = end_ind
			while ac_sums[pivot_sum_ind] != cur_sum:
				cur_ac_sums.remove(ac_sums[pivot_sum_ind])
				pivot_sum_ind += 1
			pivot_sum_ind += 1
			begin_ind = pivot_sum_ind + 1
		else:
			cur_ac_sums.add(cur_sum)
	end_ind = n + 1
	good_l = end_ind - begin_ind
	intersection_l = prev_end_ind - begin_ind
	answ += good_l * (good_l + 1) // 2 - intersection_l * (intersection_l + 1) // 2
	return answ
n = int(input())
a = list(map(int, input().split()))
answ = Sol(n, a)
print(answ)


import sys

def func(n, li):
	sum1 = []
	(ele, nextval) = (0, {})
	for i in range(n):
		ele += li[i]
		sum1.append(ele)
		nextval[ele] = sys.maxsize
	maxR = n - 1
	(ans, note) = (0, sys.maxsize)
	for i in range(n - 1, -1, -1):
		if sum1[i] == 0:
			note = i
		if i == 0:
			maxR = min(maxR, note - 1)
		elif i != 0:
			nextval[sum1[i]] = i
			maxR = min(maxR, nextval[sum1[i - 1]] - 1)
		ans += maxR - i + 1
	print(ans)
	return
n = int(input())
li = [int(x) for x in input().split()]
func(n, li)


from sys import stdin
input = stdin.readline
R = lambda : list(map(int, input().split()))
(n, a) = (int(input()), R())
(mp, sm) = ({0: -1}, 0)
(cc, pp) = (0, 0)
for i in range(n):
	sm += a[i]
	p = mp[sm] + 2 if sm in mp else 0
	if a[i] == 0:
		p = i + 1
	mp[sm] = i
	pp = max(pp, p)
	cc += i - pp + 1
print(cc)


from bisect import bisect_left as bl
for _ in range(1):
	n = int(input())
	a = list(map(int, input().split()))
	pre = [0]
	d = {}
	for i in range(n):
		pre.append(pre[-1] + a[i])
	ans = 0
	mi = n
	for i in range(n, 0, -1):
		d[pre[i]] = i
		mi = min(mi, d.get(pre[i - 1], n + 1) - 1)
		ans += mi - i + 1
	print(ans)


from collections import defaultdict

def solve(arr, n):
	ma = defaultdict(list)
	ma[0].append(-1)
	p = [arr[i] for i in range(n)]
	for i in range(1, n):
		p[i] += p[i - 1]
	(cnt, lst) = (0, -1)
	for i in range(n):
		if ma[p[i]]:
			lst = max(lst, ma[p[i]][-1] + 1)
		cnt += i - lst
		ma[p[i]].append(i)
	return cnt

def main():
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ret = solve(arr, n)
	print(ret)
main()


n = int(input())
a = [int(i) for i in input().split()]
ss = [0]
for ai in a:
	ss.append(ss[-1] + ai)
si = {0: 0}
left = 0
count = 0
for i in range(1, len(ss)):
	if ss[i] in si:
		left = max(left, si[ss[i]] + 1)
	si[ss[i]] = i
	count += i - left
print(count)


from collections import defaultdict
n = int(input())
a = [0] * (n + 1)
for (i, v) in enumerate(input().split()):
	a[i + 1] = a[i] + int(v)
ans = 0
d = defaultdict(int)
d[0] = 1
j = 0
for i in range(n):
	while j < n and (not d[a[j + 1]]):
		j += 1
		d[a[j]] += 1
	ans += j - i
	d[a[i]] -= 1
print(ans)


from bisect import bisect_left
from itertools import accumulate

def f(x, y):
	k = y - x
	return k * (k + 1) // 2

def go():
	n = int(input())
	a = list(map(int, input().split()))
	prev = 0
	res = 0
	for (i, aa) in enumerate(a):
		if aa == 0:
			if i > prev:
				res += method_name(a[prev:i], i - prev)
			prev = i + 1
	if prev < n:
		res += method_name(a[prev:], n - prev)
	return res

def method_name(a, n):
	s = sum(a)
	up = [0] + list(accumulate(a))
	down = list(reversed(list(accumulate(reversed(a))))) + [0]
	ddown = {}
	for (i, dd) in reversed(list(enumerate(down))):
		ddown.setdefault(dd, []).append(i)
	ranges = []
	for (i, u) in enumerate(up):
		v = s - u
		if v in ddown:
			matches = ddown[v]
			while matches and matches[-1] <= i:
				matches.pop()
			if matches:
				ranges.append((i, matches[-1]))
	rranges = sorted(ranges, key=lambda x: x[1])
	mclos = -1
	rem = set()
	for (ra, rb) in rranges:
		if ra <= mclos:
			rem.add((ra, rb))
		else:
			mclos = max(mclos, ra)
	ranges = [r for r in ranges if r not in rem]
	res = 0
	for r in range(len(ranges) - 1):
		res += f(ranges[r][0] + 1, ranges[r + 1][1] - 1)
	if ranges:
		res += f(0, ranges[0][1] - 1)
		res += f(ranges[-1][0] + 1, n)
	else:
		res = f(0, n)
	for (ra, rb) in ranges:
		res -= f(ra, rb - 2)
	return res
t = 1
ans = []
for _ in range(t):
	ans.append(str(go()))
print('\n'.join(ans))


n = int(input())
seen = dict()
seen[0] = 0
out = 0
l = list(map(int, input().split()))
curr = 0
bestCurr = 0
for i in range(n):
	curr += l[i]
	if curr in seen:
		bestCurr = min(bestCurr + 1, i - seen[curr])
	else:
		bestCurr += 1
	out += bestCurr
	seen[curr] = i + 1
print(out)


from collections import defaultdict
input_n = int(input())
input_list = list(map(int, input().split()))
dic = defaultdict(lambda : -2)
(count, ans, l) = (0, 0, 0)
dic[0] = -1
for _ in range(len(input_list)):
	count += input_list[_]
	if dic[count] != -2:
		l = max(l, dic[count] + 2)
	dic[count] = _
	ans += _ + 1 - l
print(ans)


import sys
n = int(input())
a = [0] + [int(i) for i in input().split()]
mx = 0
ps = 0
ans = 0
sdict = {0: 0}
for i in range(1, n + 1):
	ps += a[i]
	if ps in sdict.keys():
		if ps == 0 and sdict[0] == -1:
			mx = max(mx, sdict[ps] + 1)
		else:
			mx = max(mx, sdict[ps] + 1)
	sdict[ps] = i
	ans = ans + i - mx
print(ans)


printn = lambda x: print(x, end='')
inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
inm = lambda : map(int, input().split())
ins = lambda : input().strip()
DBG = True
BIG = 10 ** 18
R = 10 ** 9 + 7

def ddprint(x):
	if DBG:
		print(x)
n = inn()
a = inl()
a.append(0)
acc = [0] * (n + 2)
for i in range(1, n + 2):
	acc[i] = acc[i - 1] + a[i - 1]
sm = 0
stt = 0
h = {acc[0]: 1}
for i in range(1, n + 2):
	if acc[i] not in h:
		h[acc[i]] = 1
	else:
		while stt < i:
			sm += i - stt - 1
			found = acc[stt] == acc[i]
			del h[acc[stt]]
			stt += 1
			if found:
				break
		h[acc[i]] = 1
print(sm)


from collections import defaultdict
n = int(input())
aa = list(map(int, input().split()))
pos = defaultdict(list)
cursum = 0
for (i, a) in enumerate(aa):
	cursum += a
	pos[cursum].append(i)
cursum = 0
ai = defaultdict(int)
zeroseg = []
for (i, a) in enumerate(aa):
	pa = pos[cursum]
	if pa:
		while ai[cursum] < len(pa) and pa[ai[cursum]] < i:
			ai[cursum] += 1
		if ai[cursum] < len(pa):
			end = pa[ai[cursum]]
			while zeroseg and zeroseg[-1][1] >= end:
				zeroseg.pop()
			zeroseg.append((i, end))
	cursum += a
ans = 0
zerosegi = 0
for (i, a) in enumerate(aa):
	while zerosegi < len(zeroseg) and zeroseg[zerosegi][0] < i:
		zerosegi += 1
	if zerosegi == len(zeroseg):
		ans += n - i
	else:
		ans += zeroseg[zerosegi][1] - i
print(ans)


n = int(input())
seq = [int(x) for x in input().split()]
prefix = [0 for _ in range(n + 1)]
for i in range(n):
	prefix[i + 1] = prefix[i] + seq[i]
ans = 0
p = 0
s = {0}
for i in range(n):
	for _ in range(p, n):
		if prefix[p + 1] in s:
			break
		p += 1
		s.add(prefix[p])
	ans += p - i
	s.remove(prefix[i])
print(ans)


n = int(input())
d = {}
ar = list(map(int, input().split()))
pref = [0] * n
ans = 0
d = {}
uk = -1
pref[0] = ar[0]
d[0] = -1
for i in range(1, n):
	pref[i] = pref[i - 1] + ar[i]
for i in range(n):
	if pref[i] in d:
		uk = max(uk, d.get(pref[i]) + 1)
	ans += i - uk
	d[pref[i]] = i
print(ans)


import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict, deque, Counter
from bisect import *
from math import sqrt
import math
from itertools import permutations

def main():
	n = int(input())
	a = list(map(int, input().split()))
	c = [0]
	for i in a:
		c.append(c[-1] + i)
	(ans, i, j) = (0, 0, 0)
	b = set()
	b.add(0)
	while i < n:
		while j < n and c[j + 1] not in b:
			j += 1
			b.add(c[j])
		ans += j - i
		b.discard(c[i])
		i += 1
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
I = lambda : list(map(int, input().split()))
(n,) = I()
l = [0] + I()
for i in range(1, n + 1):
	l[i] += l[i - 1]
f = {}
m = 0
ans = 0
for i in range(n + 1):
	if l[i] in f:
		m = max(m, f[l[i]] + 1)
	ans += i - m
	f[l[i]] = i
print(ans)


n = int(input())
arr = [int(i) for i in input().split()]
for i in range(1, n):
	arr[i] += arr[i - 1]
dic = {}
dic[0] = [-1]
for i in range(n):
	if arr[i] in dic:
		dic[arr[i]].append(i)
	else:
		dic[arr[i]] = [i]
temp = [0] * n
endly = {}
for a in dic:
	if len(dic[a]) >= 2:
		for i in range(1, len(dic[a])):
			temp[dic[a][i]] = -1
			if dic[a][i] in endly:
				endly[dic[a][i]].append(dic[a][i - 1] + 1)
			else:
				endly[dic[a][i]] = [dic[a][i - 1] + 1]
l = 0
r = 0
count = 0
while r < n:
	if temp[r] == -1:
		l = max(max(endly[r]) + 1, l)
	count += r - l + 1
	r += 1
print(count)


def main():
	n = int(input())
	a = [int(i) for i in input().split(' ')]
	p = [0] * (n + 1)
	s = set()
	ans = 0
	for i in range(n):
		p[i + 1] = p[i] + a[i]
	s.add(0)
	end = 0
	for i in range(n):
		while end < n and p[end + 1] not in s:
			end += 1
			s.add(p[end])
		ans += end - i
		s.remove(p[i])
	print(ans)
main()


def solve(a):
	n = len(a)
	prefix = [0] * (n + 1)
	for i in range(n):
		prefix[i + 1] = prefix[i] + a[i]
	(begin, end) = (0, 0)
	res = 0
	s = set([0])
	while begin < n:
		while end < n and prefix[end + 1] not in s:
			end += 1
			s.add(prefix[end])
		res += end - begin
		s.remove(prefix[begin])
		begin += 1
	return res
n = int(input())
a = [int(i) for i in input().split()]
print(solve(a))


from math import *
from sys import *
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
curr = 0
d = {}
d[0] = -1
maxind = 0
ans = 0
for i in range(n):
	curr += a[i]
	if curr in d:
		maxind = max(maxind, d[curr] + 2)
	d[curr] = i
	ans += i - maxind + 1
print(ans)


n = int(input())
arr = list(map(int, input().split(' ')))
prefix_sum = [0]
prefix_set = set()
prefix_set.add(0)
for i in range(len(arr)):
	prefix_sum.append(prefix_sum[i] + arr[i])
(i, j, results) = (0, 0, 0)
while i < n:
	while j < n and prefix_sum[j + 1] not in prefix_set:
		j += 1
		prefix_set.add(prefix_sum[j])
	results += j - i
	prefix_set.remove(prefix_sum[i])
	i += 1
print(results)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
m = {}
n = int(input())
a = list(map(int, input().split()))
m[0] = 0
for i in range(1, n):
	a[i] += a[i - 1]
ans = 0
curMax = -1
for i in range(n):
	val = m.get(a[i], -1)
	curMax = max(curMax, val)
	ans += i - curMax
	m[a[i]] = i + 1
print(ans)


import sys
import math
input = sys.stdin.buffer.readline
mod = 998244353

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
t = 1
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	pref = [0] * (n + 1)
	pref[0] = l[0]
	d = {}
	lef = -1
	ans = 0
	for i in range(n):
		if l[i] == 0:
			lef = i
		if i != 0:
			pref[i] = pref[i - 1] + l[i]
		if d.get(abs(pref[i]), -1) == -1:
			d[abs(pref[i])] = []
		if len(d[abs(pref[i])]) >= 1:
			lef = max(lef, d[abs(pref[i])][-1] + 1)
		d[abs(pref[i])].append(i)
		if pref[i] == 0:
			lef = max(lef, 0)
		ans += i - lef
	print(ans)


from itertools import accumulate
import sys
from collections import defaultdict
import bisect
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
acc = [0] + list(accumulate(a))
dc = defaultdict(int)
rng = []
for i in range(n + 1):
	if dc[acc[i]]:
		rng.append([dc[acc[i]], i])
		dc[acc[i]] = i + 1
	else:
		dc[acc[i]] = i + 1
if not rng:
	print((n + 1) * n // 2)
	exit()
rng.sort()
for i in range(len(rng) - 1)[::-1]:
	rng[i][1] = min(rng[i][1], rng[i + 1][1])
rng1 = list(zip(*rng))[0]
ans = 0
for i in range(1, n + 1):
	x = bisect.bisect_left(rng1, i)
	if x == len(rng1):
		ans += n - i + 1
	else:
		ans += n - i - (n - rng[x][1])
print(ans)


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def main():
	n = int(input().strip())
	A = [int(s) for s in input().strip().split()]
	dp = {0: -1}
	i = -1
	s = 0
	result = 0
	for (j, a) in enumerate(A):
		s += a
		if s in dp:
			i = max(i, dp[s] + 1)
		result += j - i
		dp[s] = j
	print(result)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
from itertools import accumulate
from collections import defaultdict
n = int(input())
A = list(map(int, input().split()))
S = [0] + list(accumulate(A))
D = defaultdict(list)
for i in range(n + 1):
	D[S[i]].append(i)
B = [n] * (n + 1)
for d in D:
	for i in range(len(D[d]) - 1):
		B[D[d][i]] = min(B[D[d][i]], D[d][i + 1] - 1)
for i in range(n):
	if A[i] == 0:
		B[i] = i
ANS = 0
for i in range(n - 1, -1, -1):
	ANS += B[i] - i
	B[i - 1] = min(B[i - 1], B[i])
print(ANS)


n = int(input())
l = list(map(int, input().split()))
start = end = c = 0
v = 1
s = 0
d = {}
d[0] = 1
for i in range(len(l)):
	s += l[i]
	if s in d:
		v = max(v, d[s] + 1)
	d[s] = i + 2
	c += i + 2 - v
print(c)


def main():
	import sys
	input = sys.stdin.readline
	N = int(input())
	A = list(map(int, input().split()))
	S = [0] * (N + 1)
	for (i, a) in enumerate(A):
		S[i + 1] = S[i] + a
	ans = 0
	seen = set()
	seen.add(0)
	r = 1
	for l in range(1, N + 1):
		if A[l - 1] == 0:
			r = l + 1
			seen = set()
			seen.add(S[l])
			continue
		if r <= N:
			while S[r] not in seen:
				seen.add(S[r])
				r += 1
				if r == N + 1:
					break
		ans += r - l
		seen.remove(S[l - 1])
	print(ans)
main()


n = int(input())
nums = list(map(int, input().split()))
pre_sum = [0] * len(nums)
pre = 0
for (idx, num) in enumerate(nums):
	pre += num
	pre_sum[idx] = pre
count = {}
for (idx, num) in enumerate(pre_sum):
	if num != 0:
		count[num] = count.get(num, [])
	else:
		count[num] = count.get(num, [-1])
	count[num].append(idx)
intervals = []
for num in count:
	if len(count[num]) > 1:
		for i in range(len(count[num]) - 1):
			intervals.append((count[num][i] + 1, count[num][i + 1]))
intervals.sort(key=lambda x: x[1])
cur_inter = 0
ans = 0
for i in range(n):
	while cur_inter < len(intervals) and i > intervals[cur_inter][0]:
		cur_inter += 1
	if cur_inter == len(intervals):
		ans += n - i
	else:
		ans += intervals[cur_inter][1] - i
print(ans)


from collections import Counter
n = int(input())
a = list(map(int, input().split()))
s = [0]
for x in a:
	s.append(s[-1] + x)
c = Counter()
c[0] += 1
cur = 1
ans = 0
for i in range(n):
	while cur < n + 1 and c[s[cur]] == 0:
		c[s[cur]] += 1
		cur += 1
	ans += cur - i - 1
	if cur == i + 1:
		c[s[cur]] += 1
	cur = max(cur, i + 2)
	c[s[i]] -= 1
print(ans)


n = int(input())
arr = [int(c) for c in input().split()]
arr.insert(0, 0)
sumsofar = 0
dic = {0: 0}
h = -1
ans = 0
for i in range(1, n + 1):
	sumsofar = sumsofar + arr[i]
	if sumsofar in dic:
		h = max(h, dic[sumsofar])
	ans += i - h - 1
	dic[sumsofar] = i
print(ans)


def convertArrayToInt(A):
	for i in range(0, len(A), 1):
		A[i] = int(A[i])
	return A

def OrderN2LogNSolution(A):
	R = []
	ans = 0
	for i in range(0, len(A), 1):
		prefixSum = 0
		ps_set = {0}
		flag = 0
		for j in range(i, len(A), 1):
			prefixSum += A[j]
			if prefixSum in ps_set:
				ans += j - i
				flag = 1
				break
			ps_set.add(prefixSum)
		if flag == 0:
			ans += j - i + 1
	return ans

def OrderNLogNSolution(A):
	prefixSum = 0
	hashMap = {}
	hashMap[0] = -1
	closestLeftIndex = -1
	ans = 0
	for i in range(0, len(A), 1):
		prefixSum += A[i]
		if prefixSum in hashMap:
			closestLeftIndex = max(closestLeftIndex, hashMap[prefixSum] + 1)
		ans += i - closestLeftIndex
		hashMap[prefixSum] = i
	return ans
length = int(input())
A = []
X = input().split()
A = convertArrayToInt(X)
ans = OrderNLogNSolution(A)
print(ans)


def solve(n, a):
	d = {0: -1}
	s = 0
	res = 0
	j = -1
	for i in range(n):
		s += a[i]
		if d.get(s) != None:
			j = max(d[s] + 1, j)
		d[s] = i
		res += i - j
	return res

def main():
	n = int(input())
	a = [int(x) for x in input().split()]
	res = solve(n, a)
	print(res)
main()


from collections import defaultdict
n = int(input())
ar = list(map(int, input().split()))
m = defaultdict(lambda : -1)
m[0] = -1
st = -1
pre = []
d = 0
ans = 0
for i in range(n):
	d += ar[i]
	pre += [d]
for i in range(n):
	if m[pre[i]] != -1 or pre[i] == 0:
		st = max(st, m[pre[i]] + 1)
	m[pre[i]] = i
	ans += i - st
print(ans)


t = 1
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	dict = {}
	sum = 0
	dict[0] = -1
	ans = 0
	nearest = -1
	for i in range(n):
		sum += a[i]
		if dict.get(sum) is None:
			ans += i - nearest
		else:
			p = dict[sum]
			p = max(dict[sum] + 1, nearest)
			ans += i - p
			nearest = p
		dict[sum] = i
	print(ans)


n = int(input())
arr = [int(n) for n in input().split()]
hash_map = {0: 0}
total = 0
bad = 0
good = 0
for i in range(1, n + 1):
	total += arr[i - 1]
	if total in hash_map:
		bad = max(bad, hash_map[total] + 1)
	hash_map[total] = i
	good += i - bad
print(good)


import os
import sys
from io import BytesIO, IOBase
import threading
from collections import defaultdict, Counter
from math import factorial as fac

def main():
	for _ in range(1):
		n = int(input())
		arr = list(map(int, input().split()))
		pref = [0]
		for i in arr:
			pref.append(pref[-1] + i)
		start = 0
		d = dict()
		ans = 0
		for (ind, ele) in enumerate(pref):
			if ele in d and d[ele] >= start:
				start = d[ele] + 1
			ans += ind - start
			d[ele] = ind
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
N = int(sys.stdin.readline())
list_a = list(map(int, sys.stdin.readline().split()))
list_sum = [0] * (N + 1)
for i in range(N):
	list_sum[i + 1] = list_sum[i] + list_a[i]
result = 0
set_count = set()
set_count.add(0)
s = e = 0
ans = 0
while s < N:
	while e < N and (not list_sum[e + 1] in set_count):
		e += 1
		set_count.add(list_sum[e])
	ans += e - s
	set_count.remove(list_sum[s])
	s += 1
print(ans)


n = int(input())
l = list(map(int, input().split()))
arr = [0]
d = {}
for i in range(1, n + 1):
	arr.append(arr[i - 1] + l[i - 1])
sum = 0
j = n
for i in range(n, -1, -1):
	if arr[i] in d:
		j = min(j, d[arr[i]] - 1)
	sum += j - i
	d[arr[i]] = i
print(sum)


n = int(input())
a = list(map(int, input().split()))
ans = 0
s = {0: -1}
tmp = 0
last = -1
for i in range(n):
	tmp += a[i]
	if tmp in s:
		last = max(last, s[tmp] + 1)
	ans += i - last
	s[tmp] = i
print(ans)


import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
from functools import lru_cache
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
if os.path.exists('out.txt'):
	sys.stdout = open('out.txt', 'w')

def input():
	return sys.stdin.readline()

def mapi(arg=0):
	return map(int if arg == 0 else str, input().split())
n = int(input())
a = list(mapi())
res = n * (n + 1) // 2
cnt = 0
sm = 0
res = 0
mp = defaultdict(list)
pf = [0] * (n + 1)
pf[1] = a[0]
for i in range(1, n):
	pf[i + 1] = pf[i] + a[i]
mp = defaultdict(list)
k = 0
mp[k] = [-1]
count = 0
tmp1 = 0
newidx = True
(i, j) = (0, 0)
while i < n:
	while j < n:
		if len(mp[k]) == 2:
			count += n - j
			break
		if newidx:
			k += a[j]
			mp[k].append(j)
		if len(mp[k]) == 2:
			count += n - j
			break
		j += 1
		newidx = True
	mp[tmp1] = mp[tmp1][1:]
	tmp1 = tmp1 + a[i]
	i += 1
	newidx = False
res = n * (n + 1) // 2 - count
print(res)


a = int(input())
la = list(map(int, input().split()))
partsum = [la[0] for i in range(a)]
for i in range(1, a):
	partsum[i] = partsum[i - 1] + la[i]
good = [1 for i in range(a)]
if la[0] == 0:
	good[0] = 0
clear = [True for i in range(a)]
parts = {partsum[0]}
for i in range(1, a):
	if partsum[i] not in parts:
		parts.add(partsum[i])
	else:
		clear[i] = False
for i in range(1, a):
	good[i] = good[i - 1] + 1
	if not clear[i]:
		for j in range(1, good[i - 1] + 2):
			if i >= j and partsum[i - j] == partsum[i]:
				good[i] = j - 1
				break
	if partsum[i] == 0:
		good[i] = min(good[i], i)
print(sum(good))


import bisect
n = int(input())
a = list(map(int, input().split()))
itr = 0
while itr < n and a[itr] == 0:
	itr += 1
if itr == n:
	print(0)
else:
	a = a[itr:]
	pre = []
	pre.append(a[0])
	d = dict()
	d[0] = list()
	d[0].append(-1)
	d[a[0]] = list()
	d[a[0]].append(0)
	for i in range(1, len(a)):
		pre.append(pre[i - 1] + a[i])
		if d.get(pre[i], None) == None:
			d[pre[i]] = list()
		d[pre[i]].append(i)
	ans = 0
	last = -2
	for i in range(len(a)):
		if a[i] == 0:
			last = i
			continue
		if len(d.get(pre[i])) == 1:
			if last == -2:
				ans = ans + i + 1
			else:
				ans = ans + i - last
		else:
			temp = d.get(pre[i])
			ind = bisect.bisect(temp, i)
			if ind == 1:
				if last == -2:
					ans = ans + i + 1
				else:
					ans = ans + i - last
			elif temp[ind - 2] >= last:
				length = i - temp[ind - 2] - 1
				ans = ans + length
				last = temp[ind - 2] + 1
				if last == -1:
					last += 1
			else:
				ans = ans + i - last
	print(ans)


from collections import defaultdict
n = int(input())
li = [-2]
ar = list(map(int, input().split()))
dd = defaultdict(lambda : -2)
a = 0
s = 0
for j in range(n):
	a += ar[j]
	if a == 0:
		if len(li) == 1:
			li.append(-1)
			s += n - j
	if dd[a] != -2:
		b = li[-1]
		i = dd[a]
		if i <= b:
			dd[a] = j
			continue
		y = i - b
		s += y * (n - j)
		li.append(i)
	dd[a] = j
x = n * (n + 1) / 2
print(int(x) - s)


def solve(a):
	n = len(a)
	ru = [0] * (n + 1)
	for i in range(n):
		ru[i + 1] = ru[i] + a[i]
	next_ = [n] * (n + 1)
	memo = {}
	for i in range(n + 1)[::-1]:
		if ru[i] in memo:
			next_[i] = memo[ru[i]] - 1
		if i != n:
			next_[i] = min(next_[i + 1], next_[i])
		memo[ru[i]] = i
	ans = 0
	for i in range(n)[::-1]:
		ans += next_[i] - i
	return ans
import sys
input = sys.stdin.readline
n = int(input())
b = list(map(int, input().split()))
ans = [[] for i in range(n)]
pos = 0
for i in range(n):
	if b[i] == 0:
		pos += 1
	else:
		ans[pos].append(b[i])
res = 0
for i in ans:
	res += solve(i)
print(res)


input()
ns = [int(x) for x in input().split()]
loc = {0: -1}
start = -1
acc = 0
result = 0
for (i, v) in enumerate(ns):
	acc += v
	if acc in loc:
		start = max(start, loc[acc] + 1)
	result += i - start
	loc[acc] = i
print(result)


n = int(input())
a = list(map(int, input().strip().split()))
d = {0: 0}
l = -1
cumulative_array = [0]
for i in range(n):
	cumulative_array.append(cumulative_array[-1] + a[i])
ans = 0
for i in range(1, n + 1):
	c = cumulative_array[i]
	if c in d:
		l = max(l, d[c])
	d[c] = i
	ans += i - l - 1
print(ans)


n = int(input())
last = 0
o = {0: -1}
t = 0
rs = 0
a = [int(x) for x in input().split()]
for (i, ai) in enumerate(a):
	rs += ai
	if rs in o:
		last = max(last, o[rs] + 2)
	o[rs] = i
	t += i - last + 1
print(t)


from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
from collections import defaultdict as dd, deque

def data():
	return sys.stdin.readline().strip()

def mdata():
	return map(int, data().split())
mod = int(1000000000.0 + 7)
n = int(data())
a = list(mdata())
d = dd(int)
d1 = dd(int)
ans = n * (n + 1) // 2
s = 0
i = 0
ind = 0
while i < n:
	s += a[i]
	if s == 0:
		ans -= n - i
		i = ind
		d = dd(int)
		d1 = dd(int)
		ind += 1
		i = ind
		continue
	if d[s] != 0:
		ans -= (d1[s] + 1 - ind) * (n - i - 1) + (d1[s] + 1 - ind)
		ind = d1[s] + 1
		i = ind
		d = dd(int)
		d1 = dd(int)
		s = 0
		continue
	d[s] += 1
	d1[s] = i
	i += 1
print(ans)


from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
d = defaultdict(int)
s = 0
left = -1
ans = 0
d[0] = 0
max_l = 0
for i in range(n):
	s += a[i]
	if s in d.keys():
		left = max(left, d[s] + 1)
		max_l = left
	else:
		left = max_l
	d[s] = i + 1
	ans += i - left + 1
print(ans)


n = int(input())
aa = [0] + [int(i) for i in input().split()]
(ss, beg, ans) = (0, 0, 0)
dic = dict()
for i in range(0, n + 1):
	ss += aa[i]
	if ss in dic:
		beg = max(beg, dic[ss] + 1)
	ans += i - beg
	dic[ss] = i
print(ans)


n = int(input())
a = list(map(int, input().split()))
sums = []
s = 0
sums.append([0, 0])
for i in range(n):
	s += a[i]
	sums.append([s, i + 1])
sums = sorted(sums)
last = [-1] * (n + 1)
for i in range(n):
	if sums[i][0] == sums[i + 1][0]:
		last[sums[i + 1][1]] = sums[i][1]
result = 0
l = -1
for i in range(1, n + 1):
	l = max(l, last[i])
	result = result + (i - l - 1)
print(result)


import sys
n = int(input())
a = [0] + [int(i) for i in input().split()]
ans = 0
sm = 0
mx = 0
mp = {0: -1}
for i in range(1, n + 1):
	sm += a[i]
	if sm in mp.keys():
		if sm == 0 and mp[0] == -1:
			mx = max(1, mx)
		else:
			mx = max(mx, mp[sm] + 1)
	mp[sm] = i
	ans = ans + i - mx
print(ans)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
from itertools import permutations
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
a = list(map(int, input().split()))
di = {}
di[0] = 0
ans = 0
total = 0
sub = -1
for i in range(n):
	total += a[i]
	if total in di:
		sub = max(sub, di[total])
	di[total] = i + 1
	ans += i - sub
print(ans)


from __future__ import division, print_function
from collections import Counter
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def main():
	n = int(input())
	a = [int(x) for x in input().split()]
	result = 0
	prefix = [0]
	for val in a:
		prefix.append(prefix[-1] + val)
	seen = set([0])
	r = 0
	for l in range(n):
		while r < n and prefix[r + 1] not in seen:
			seen.add(prefix[r + 1])
			r += 1
		result += r - l
		seen.remove(prefix[l])
	print(result)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
l = list(map(int, input().split()))
a = [0]
lis = []
d = {0: -1}
for i in range(n):
	a.append(a[-1] + l[i])
	if d.get(a[-1]) != None:
		lis.append((d[a[-1]] + 1, i))
		d[a[-1]] = i
	else:
		d[a[-1]] = i
ans = 0
lis = lis[::-1]
for i in range(n):
	flag = 0
	j = len(lis) - 1
	while j >= 0:
		if lis[j][0] >= i:
			ans += lis[j][1] - i
			flag = 1
			break
		else:
			lis.pop()
		j -= 1
	if flag == 0:
		ans += n - i
print(ans)


def sumoflength(arr, n):
	s = set()
	j = 0
	ans = 0
	for i in range(n):
		while j < n and arr[j] not in s:
			s.add(arr[j])
			j += 1
		ans += j - i - 1
		s.remove(arr[i])
	return ans
n = int(input().strip())
numbers = list(map(int, input().strip().split()))
prefsum = [0 for i in range(n + 1)]
prefsum[0] = 0
for q in range(1, n + 1):
	prefsum[q] = prefsum[q - 1] + numbers[q - 1]
print(sumoflength(prefsum, n + 1))


n = int(input())
a = list(map(int, input().split()))
aux = [0] * (n + 1)
for i in range(n):
	aux[i + 1] = aux[i] + a[i]
total = 0
l = 0
r = 0
s = set({})
d = {}
while r <= n:
	if aux[r] in s and l <= d[aux[r]]:
		total += (r - l) * (r - l - 1) // 2 - (r - d[aux[r]] - 1) * (r - d[aux[r]] - 2) // 2
		l = d[aux[r]] + 1
		d[aux[r]] = r
	else:
		s.add(aux[r])
		d[aux[r]] = r
	r += 1
total += (r - l) * (r - l - 1) // 2
print(total)


n = int(input())
s = [0]
for x in map(int, input().split()):
	s.append(s[-1] + x)
se = set()
i = j = 0
ans = 0
while j != len(s):
	while j != len(s) and s[j] not in se:
		se.add(s[j])
		j += 1
	if j == len(s):
		break
	se.remove(s[i])
	i += 1
	ans += j - i
j -= i + 1
ans += (1 + j) * j // 2
print(ans)


def solve(a):
	seen = {0: -1}
	res = curr = mx = 0
	for (i, x) in enumerate(a):
		curr += x
		if curr in seen:
			mx = max(mx, seen[curr] + 2)
		res += mx
		seen[curr] = i
	return len(a) * (len(a) + 1) // 2 - res
input()
a = list(map(int, input().split()))
print(solve(a))


import sys
input = sys.stdin.readline
(N,) = map(int, input().split())
A = [0] + list(map(int, input().split()))
from itertools import accumulate
A = list(accumulate(A))
vs = dict()
r = 0
j = -1
for i in range(N + 1):
	a = A[i]
	if a in vs:
		j = max(j, vs[a])
	vs[a] = i
	r += i - j - 1
print(r)


import sys
inp = sys.stdin.readline

def input():
	return inp().strip()
flush = sys.stdout.flush

def iin():
	return int(input())

def lin():
	return list(map(int, input().split()))

def main():
	T = 1

	def fn(n):
		return n * (n + 1) // 2
	for _ in range(T):
		n = iin()
		a = lin()
		a1 = [0] + a[:]
		for i in range(1, n + 1):
			a1[i] += a1[i - 1]
		dc = {}
		ans = fn(n)
		pv = 0
		for i in range(n + 1):
			if a1[i] in dc:
				if pv > dc[a1[i]]:
					continue
				ans -= (1 + n - i) * (dc[a1[i]] - pv + 1)
				pv = dc[a1[i]] + 1
			dc[a1[i]] = i
		print(ans)
main()


import sys
input = sys.stdin.buffer.readline
from bisect import bisect_left

def prog():
	n = int(input())
	array = list(map(int, input().split()))
	psum = [0]
	for i in range(n):
		psum.append(psum[-1] + array[i])
	occurences = {}
	for i in range(n + 1):
		if psum[i] in occurences:
			occurences[psum[i]].append(i)
		else:
			occurences[psum[i]] = [i]
	for a in occurences.values():
		a.sort()
	left = 0
	total_good = 0
	for right in range(1, n + 1):
		total = psum[right]
		closest = bisect_left(occurences[total], right) - 1
		if closest != -1:
			new_left = occurences[total][closest] + 1
			left = max(new_left, left)
		total_good += right - left
	print(total_good)
prog()


from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))

def solve():
	n = ri()
	A = rl()
	lastseen = {0: -1}
	lastbad = {}
	prev = 0
	for (i, a) in enumerate(A):
		partial = a + prev
		prev = partial
		if partial in lastseen:
			lastbad[i] = lastseen[partial]
		lastseen[partial] = i
	answer = 0
	lastworst = -2
	for i in range(n):
		if i in lastbad:
			lastworst = max(lastworst, lastbad[i])
		answer += i - lastworst - 1
	print(answer)
mode = 'S'
if mode == 'T':
	t = ri()
	for i in range(t):
		solve()
else:
	solve()


import sys
input = sys.stdin.readline
from collections import *
n = int(input())
a = list(map(int, input().split()))
acc = 0
d = defaultdict(int)
d[0] = -1
ans = 0
m = -2
for i in range(n):
	acc += a[i]
	if acc in d:
		m = max(m, d[acc])
	ans += i - m - 1
	d[acc] = i
print(ans)


n = int(input())
arr = [int(i) for i in input().split()]
dic = {0: -1}
ans = []
s = 0
for i in range(len(arr)):
	s += arr[i]
	if s in dic:
		if len(ans) > 0 and dic[s] + 1 > ans[-1][0]:
			ans.append([dic[s] + 1, i])
		elif len(ans) == 0:
			ans.append([dic[s] + 1, i])
	dic[s] = i
sm = 0
for i in range(len(ans)):
	sm += (ans[i][0] + 1) * (n - ans[i][1])
	if i != 0:
		sm -= min(ans[i - 1][0] + 1, ans[i][0] + 1) * min(n - ans[i][1], n - ans[i - 1][1])
print(n * (n + 1) // 2 - sm)


import sys
input = sys.stdin.readline
n = int(input())
L = list(map(int, input().split()))
M = [0]
for i in L:
	M.append(M[-1] + i)
d = dict()
cklist = [-1] * n
ckd = -1
for i in range(n + 1):
	if M[i] not in d:
		d[M[i]] = [i]
	else:
		for j in range(ckd + 1, d[M[i]][-1] + 1):
			if cklist[j] == -1 or cklist[j] > i:
				cklist[j] = i
		ckd = d[M[i]][-1]
		d[M[i]].append(i)
c = n * (n + 1)
c //= 2
for i in range(n):
	if cklist[i] == -1:
		continue
	else:
		k = cklist[i]
		c -= n - k + 1
print(c)


n = int(input())
a = list(map(int, input().split()))
ans = 0
pre = {0: -1}
tmp = 0
pp = -1
for i in range(n):
	tmp += a[i]
	if tmp in pre:
		pp = max(pp, pre[tmp] + 1)
	ans += i - pp
	pre[tmp] = i
print(ans)


while True:
	try:

		def soln(a):
			elmn = {0: 0}
			gdElPos = sAry = sum = 0
			for i in range(len(a)):
				sum += a[i]
				if sum in elmn:
					gdElPos = max(gdElPos, elmn[sum] + 1)
				elmn[sum] = i + 1
				sAry += i + 1 - gdElPos
			print(sAry)

		def read():
			n = int(input())
			a = list(map(int, input().split()))
			soln(a)
		if __name__ == '__main__':
			read()
	except EOFError:
		break


from collections import defaultdict
n = int(input())
a = [int(el) for el in input().split()]
psum = [0 for i in range(n)]
psum[0] = a[0]
for i in range(1, n):
	psum[i] = psum[i - 1] + a[i]
d = defaultdict(int)
res = 0
pos = 0
d[0] = 0
for i in range(len(psum)):
	if psum[i] in d:
		pos = max(pos, d[psum[i]] + 1)
	res += i - pos + 1
	d[psum[i]] = i + 1
print(res)


from math import *
mod = 1000000007
n = int(input())
a = [int(i) for i in input().split()]
p = [0] * n
p[0] = a[0]
for i in range(1, n):
	p[i] = a[i] + p[i - 1]
ind = {}
for i in range(n):
	if p[i] not in ind:
		ind[p[i]] = [i]
	else:
		ind[p[i]].append(i)
segs = []
for k in ind:
	t = ind[k]
	x = len(t)
	if k == 0:
		segs.append([0, t[0]])
	for i in range(1, x):
		segs.append([t[i - 1] + 1, t[i]])
ans = 0
if len(segs) > 0:
	segs.sort(key=lambda x: x[1])
	segs.sort(key=lambda x: x[0])
	le = len(segs)
	p2 = [10000000] * le
	p2[-1] = segs[-1][1]
	for i in range(le - 2, -1, -1):
		p2[i] = min(p2[i + 1], segs[i][1])
	ci = 0
	for i in range(n):
		while ci < le and segs[ci][0] < i:
			ci += 1
		if ci == le:
			ans += n - i
		else:
			ans += p2[ci] - i
else:
	ans = n * (n + 1) // 2
print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()

def I():
	return list(map(int, input().split()))
n = I()[0]
a = I()
d = {0: -1}
last = -1
s = [a[0]]
ans = 0
for i in range(1, n):
	s.append(a[i] + s[-1])
for i in range(len(s)):
	if s[i] in d:
		last = max(last, d[s[i]] + 1)
	d[s[i]] = i
	ans += i - last
print(ans)


n = int(input())
a = [int(x) for x in input().strip().split()]
pos = {0: 0}
(bound, tot, ans) = (1, 0, 0)
for i in range(1, n + 1):
	tot += a[i - 1]
	if tot in pos:
		bound = max(bound, pos[tot] + 2)
	pos[tot] = i
	ans += i - bound + 1
print(ans)


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline
M = mod = 998244353

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split()]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n')]

def li3():
	return [int(i) for i in input().rstrip('\n')]
n = val()
l = li()
totgood = n * (n + 1) // 2
cnt = {}
su = ans = 0
ans = totgood
cnt[su] = 0
last = -1
for (ind, i) in enumerate(l):
	su += i
	if su in cnt and cnt[su] > last:
		left = cnt[su] - last
		last = cnt[su]
		right = n - ind
		ans -= left * right
	cnt[su] = ind + 1
cnt = {}
su = 0
print(ans)


import sys
from collections import defaultdict
input = lambda : sys.stdin.readline().strip()
n = int(input())
a = list(map(int, input().split()))
ans = 0
prev = defaultdict(int)
j = 0
b = [0] * (n + 1)
for i in range(1, n + 1):
	b[i] = b[i - 1] + a[i - 1]
for i in range(n + 1):
	prev[b[i]] += 1
	while prev[b[i]] > 1:
		prev[b[j]] -= 1
		j += 1
	ans += i - j
print(ans)


from bisect import bisect_right
n = int(input())
a = list(map(int, input().split()))
sums = {}
cs = 0
for i in range(n):
	cs += a[i]
	if cs not in sums:
		sums[cs] = []
	sums[cs].append(i)
cs = 0
from_here = []
to = []
for i in range(n):
	if cs in sums:
		possibilities = sums[cs]
		bise = bisect_right(possibilities, i)
		if bise >= len(possibilities):
			from_here.append(n - 1)
		else:
			from_here.append(possibilities[bise] - 1)
	else:
		from_here.append(n - 1)
	cs += a[i]
lmost = n - 1
cs = 0
for j in range(n - 1, -1, -1):
	if from_here[j] < lmost:
		lmost = from_here[j]
	if a[j] == 0:
		lmost = j - 1
	to.append(lmost)
to = list(reversed(to))
cs = 0
for i in range(n):
	if a[i] != 0:
		cs += to[i] - i + 1
print(cs)


from sys import stdin
from collections import defaultdict, deque
input = stdin.readline
R = lambda : list(map(int, input().split()))
(n, a) = (int(input()), R())
(mp, sm) = (defaultdict(deque), 0)
for i in range(n):
	sm += a[i]
	mp[sm].append(i)
(cc, sm) = ([0] * n, 0)
for i in range(n):
	p = mp[sm][0] if sm in mp.keys() else n
	cc[i] = p
	sm += a[i]
	mp[sm].popleft()
	if not mp[sm]:
		mp.pop(sm, None)
(res, mn) = (0, n)
for i in reversed(range(n)):
	mn = min(mn, cc[i])
	res += mn - i
print(res)


import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
acc = [0]
for ai in a:
	acc.append(acc[-1] + ai)
r = 1
cnt = defaultdict(int)
cnt[0] = 1
ans = 0
for l in range(n):
	while r < n + 1 and cnt[acc[r]] == 0:
		cnt[acc[r]] += 1
		r += 1
	ans += r - l - 1
	if l == r:
		r += 1
	cnt[acc[l]] -= 1
print(ans)


n = int(input())
array = [int(s) for s in input().split()]
prefs = {}
s = 0
left = 0
ans = 0
for i in range(1, len(array) + 1):
	s += array[i - 1]
	if array[i - 1] == 0:
		left = max(i, left)
	elif s == 0:
		if 0 not in prefs:
			left = max(1, left)
		else:
			left = max(1, prefs[0][-1] + 1)
	elif s in prefs:
		left = max(prefs[s][-1] + 1, left)
	if s in prefs:
		prefs[s].append(i)
	else:
		prefs[s] = [i]
	if array[i - 1] != 0:
		ans += i - left
print(ans)


n = int(input())
a = [0] + [int(x) for x in input().split(' ')]
ans = 0
lastocc = {0: 0}
sum = 0
soms = 0
for i in range(1, n + 1):
	sum += a[i]
	if lastocc.get(sum, -1) >= soms:
		soms = lastocc[sum] + 1
	lastocc[sum] = i
	ans += i - soms
print(ans)


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(n,) = I()
l = [0] + I()
for i in range(1, n + 1):
	l[i] += l[i - 1]
f = {}
m = 0
ans = 0
for i in range(n + 1):
	if l[i] in f:
		m = max(m, f[l[i]] + 1)
	ans += i - m
	f[l[i]] = i
print(ans)


n = int(input())
l = list(map(int, input().split()))
for i in range(1, len(l)):
	l[i] = l[i] + l[i - 1]
count = 0
used = 0
d = {}
d[0] = 0
for i in range(0, n):
	if l[i] in d:
		used = max(used, d[l[i]] + 1)
	count += i + 1 - used
	d[l[i]] = i + 1
print(count)


def inn():
	return map(int, input().split())

def cout(s):
	print(s, end='')
(n,) = inn()
a = inn()
a = [x for x in a]
s = 0
i = 0
dc = {0: -1}
pers = []
while i < n:
	s += a[i]
	a[i] = s
	if a[i] not in dc:
		dc[a[i]] = i
	else:
		pers.append((dc[a[i]] + 1, i))
		dc[a[i]] = i
	i += 1
l = -1
s = 0
for (x, y) in pers:
	if l < x:
		s += (x - l) * (n - y)
		l = x
s = n * (n + 1) / 2 - s
s = int(s)
print(s)


from sys import stdin, gettrace
if not gettrace():

	def input():
		return next(stdin)[:-1]

def main():
	n = int(input())
	aa = [int(a) for a in input().split()]
	saa = [(0, 0)] * (n + 1)
	sa = 0
	for (i, a) in enumerate(aa, 1):
		sa += a
		saa[i] = (sa, i)
	saa.sort()
	zranges = []
	for i in range(n):
		if saa[i][0] == saa[i + 1][0]:
			zranges.append((saa[i][1], saa[i + 1][1]))
	zranges.sort()
	mines = [0] * n
	mine = n + 1
	for i in range(n - 1, -1, -1):
		if zranges and zranges[-1][0] == i:
			mine = min(mine, zranges[-1][1])
			zranges.pop()
		mines[i] = mine
	count = 0
	for i in range(n):
		count += mines[i] - i - 1
	print(count)
main()


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def pow(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def gcd(a, b):
	if a == b:
		return a
	while b > 0:
		(a, b) = (b, a % b)
	return a

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]

def N():
	return int(inp())
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def YES():
	print('YES')

def NO():
	print('NO')

def Yes():
	print('Yes')

def No():
	print('No')
from collections import defaultdict

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24

def solve():
	n = N()
	ar = lis()
	pref = [0]
	for i in range(n):
		pref.append(pref[-1] + ar[i])
	st = 0
	en = 0
	c = 0
	s = set()
	s.add(0)
	while st < n:
		while en < n and pref[en + 1] not in s:
			en += 1
			s.add(pref[en])
		c += en - st
		s.remove(pref[st])
		st += 1
	print(c)
solve()


import sys, os, io
from collections import defaultdict
import bisect

def fun(a, n):
	dic = defaultdict(lambda : [])
	pa = [a[0]]
	for i in range(1, n):
		pa.append(pa[-1] + a[i])
	for i in range(len(pa)):
		dic[pa[i]].append(i)
	temp = 0
	ans = 0
	nxt = []
	for i in range(n):
		x = n
		if temp in dic:
			x = bisect.bisect_right(dic[temp], i)
			if x == len(dic[temp]):
				x = n
			else:
				x = dic[temp][x]
		temp += a[i]
		nxt.append(x)
	suff = [nxt[-1]]
	for i in range(n - 2, -1, -1):
		suff.append(min(suff[-1], nxt[i]))
	suff.reverse()
	ans = 0
	for i in range(n):
		ans += n - suff[i]
	return n * (n + 1) // 2 - ans
n = int(input())
a = [int(i) for i in input().split()]
b = []
fans = 0
for i in range(n):
	if a[i] == 0:
		if len(b) != 0:
			fans += fun(b, len(b))
			b = []
	else:
		b.append(a[i])
if len(b) > 0:
	fans += fun(b, len(b))
print(fans)


n = int(input())
arr = list(map(int, input().split(' ')))
ans = 0
sm = 0
dict = {}
dict[0] = -1
mx = 0
for i in range(1, n + 1):
	sm += arr[i - 1]
	if dict.get(sm) != None:
		if sm == 0 and dict[0] == -1:
			mx = max(mx, 1)
		else:
			mx = max(mx, dict[sm] + 1)
	dict[sm] = i
	ans += i - mx
print(ans)


import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub
input = sys.stdin.readline
INF = 2 ** 62 - 1

def read_int():
	return int(input())

def read_int_n():
	return list(map(int, input().split()))

def read_float():
	return float(input())

def read_float_n():
	return list(map(float, input().split()))

def read_str():
	return input().strip()

def read_str_n():
	return list(map(str, input().split()))

def error_print(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.time()
		ret = f(*args, **kwargs)
		e = time.time()
		error_print(e - s, 'sec')
		return ret
	return wrap

@mt
def slv(N, A):
	sa = [0]
	for a in A:
		sa.append(sa[-1] + a)
	r = 1
	c = Counter()
	c[0] += 1
	ans = 0
	for i in range(N + 1):
		for j in range(r, N + 1):
			if c[sa[j]] == 0:
				c[sa[j]] += 1
				ans += j - i
			else:
				break
		c[sa[i]] -= 1
		r = j
	return ans

def main():
	N = read_int()
	A = read_int_n()
	print(slv(N, A))
main()


n = int(input())
arr = list(map(int, input().split()))
for i in range(1, len(arr)):
	arr[i] += arr[i - 1]
arr = [0] + arr
st = 0
mp = {}
ans = 0
for (i, c) in enumerate(arr):
	if c in mp:
		st = max(st, mp[c] + 1)
		ans += i - st
	else:
		ans += i - st
	mp[c] = i
print(ans)


import sys
from math import ceil
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
n = int(ri())
a = Ri()
dic = {}
dic[0] = -1
ans = 0
flag = False
prev = -1
summ = 0
for i in range(len(a)):
	summ += a[i]
	a[i] = summ
for i in range(len(a)):
	if a[i] in dic:
		if not flag:
			flag = True
			prev = dic[a[i]]
			dic[a[i]] = i
			ans += i - prev - 1
		else:
			cprev = dic[a[i]]
			if cprev < prev:
				ans += i - prev - 1
				dic[a[i]] = i
			else:
				prev = cprev
				ans += i - prev - 1
				dic[a[i]] = i
	elif not flag:
		dic[a[i]] = i
		ans += i + 1
	else:
		dic[a[i]] = i
		ans += i - prev - 1
print(ans)


n = int(input())
a = list(map(int, input().split()))
pref = [0 for i in range(n + 1)]
for i in range(n):
	pref[i + 1] = pref[i] + a[i]
d = {}
d[0] = 0
ans = 0
used = 0
for i in range(1, n + 1):
	if pref[i] in d:
		used = max(used, d[pref[i]] + 1)
	ans += i - used
	d[pref[i]] = i
print(ans)


from collections import defaultdict
N = int(input())
arr = list(map(int, input().split()))
d = defaultdict(lambda : -2)
s = 0
ans = 0
left = 0
d[0] = -1
for i in range(len(arr)):
	s += arr[i]
	if d[s] != -2:
		left = max(left, d[s] + 2)
	d[s] = i
	ans += i + 1 - left
print(ans)


import sys, math, itertools, collections, copy
input = sys.stdin.readline
N = int(input())
arr = list(map(int, input().split()))
p = [0]
for i in range(N):
	p.append(p[-1] + arr[i])
was = set()
begin = end = 0
ans = 0
while begin < N:
	was.add(p[begin])
	end = max(end, begin)
	while end < N and p[end + 1] not in was:
		was.add(p[end + 1])
		end += 1
	ans += end - begin
	was.discard(p[begin])
	begin += 1
print(ans)


n = int(input())
A = list(map(int, input().split()))
from itertools import accumulate
B = [0] + A
B = list(accumulate(B))
s = 0
t = 0
S = set()
ans = 0
for s in range(n + 1):
	while t < n + 1 and B[t] not in S:
		S.add(B[t])
		t += 1
	ans += t - 1 - s
	if s == t:
		t += 1
	else:
		S.remove(B[s])
print(ans)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from heapq import *
from math import gcd, factorial, floor, ceil
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 10 ** 9 + 7

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def solve(case):
	n = int(inp())
	a = lis()
	curr = 0
	hash = {}
	hash[0] = -1
	maxind = 0
	ans = 0
	for i in range(n):
		curr += a[i]
		if curr in hash:
			maxind = max(maxind, hash[curr] + 2)
		hash[curr] = i
		ans += i - maxind + 1
	print(ans)
testcase(1)


I = lambda : list(map(int, input().split()))
(n,) = I()
l = [0] + I()
for i in range(1, n + 1):
	l[i] += l[i - 1]
f = {}
m = 0
ans = 0
for i in range(n + 1):
	if l[i] in f:
		m = max(m, f[l[i]] + 1)
	ans += i - m
	f[l[i]] = i
print(ans)


n = int(input())
a = list(map(int, input().split()))
dic = {}
dic[0] = -1
nsum = 0
ans = 0
ll = -2
for i in range(n):
	nsum += a[i]
	if nsum not in dic:
		ans += i - ll - 1
		dic[nsum] = i
	else:
		ll = max(dic[nsum], ll)
		ans += i - ll - 1
		dic[nsum] = i
print(ans)


from sys import stdin
n = int(stdin.readline())
cnt = 0
bad = -1
currsum = 0
suffixes = {0: 0}
for (i, x) in enumerate(map(int, stdin.readline().split())):
	currsum += x
	bad = max(bad, suffixes.get(currsum, -1))
	cnt += i - bad
	suffixes[currsum] = i + 1
print(cnt)


from _collections import deque
import sys
sys.setrecursionlimit(10000)
import math
import heapq
import bisect
inf = 2 * 10 ** 5
n = int(input())
a = list(map(int, input().split()))
p = [0]
for i in range(n):
	p.append(p[-1] + a[i])
len = 1
answer = 0
s = {0}
l = -1
for r in range(n):
	while p[r + 1] in s:
		s.discard(p[l + 1])
		l += 1
	answer += r - l
	s.add(p[r + 1])
print(answer)


def solve(a, n):
	s = 0
	sums = {}
	sums[0] = 0
	p = 0
	ans = 0
	subarrs = []
	for x in range(n):
		s = s + a[x]
		if sums.get(s) == None:
			sums[s] = x + 1
		else:
			if sums[s] + 1 >= p:
				subarrs.append((sums[s] + 1, x + 1))
				p = sums[s] + 1
			sums[s] = x + 1
	p = 1
	for x in range(len(subarrs)):
		ans = ans + (subarrs[x][0] - p + 1) * (n - subarrs[x][1] + 1)
		p = subarrs[x][0] + 1
	return int(n * (n + 1) / 2) - ans
n = int(input())
a = list(map(int, input().split()))
print(solve(a, len(a)))


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def solve(N, A):
	presum = [0]
	for v in A:
		presum.append(presum[-1] + v)
	(start, end) = (0, 0)
	ans = 0
	s = {0}
	while start < N:
		while end < N and presum[end + 1] not in s:
			end += 1
			s.add(presum[end])
		ans += end - start
		s.remove(presum[start])
		start += 1
	return ans
N = int(input())
A = [int(x) for x in input().split()]
print(solve(N, A))


import os, sys
from io import BytesIO, IOBase
from collections import defaultdict
from bisect import bisect

def main():
	n = int(input())
	a = list(map(int, input().split()))
	cul = [0]
	for i in a:
		cul.append(cul[-1] + i)
	dct = defaultdict(list)
	for (ind, val) in enumerate(cul):
		dct[val].append(ind - 1)
	(maxi, ans) = (n - 1, 0)
	for i in range(n - 2, -2, -1):
		x = cul[i + 1]
		y = bisect(dct[x], i)
		if y != len(dct[x]):
			maxi = min(maxi, dct[x][y] - 1)
		ans += maxi - i
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
x = list(map(int, input().split()))
m = {}
count = 0
v = []
(last, ans) = (-1, 0)
m[0] = -1
for i in range(n):
	count += x[i]
	if count in m:
		if m[count] + 1 > last:
			v.append([m[count] + 1, i])
			last = m[count] + 1
	m[count] = i
v.sort()
last = -1
for i in range(len(v)):
	ans += (v[i][0] - last) * (n - v[i][1])
	last = v[i][0]
print(n * (n + 1) // 2 - ans)


n = int(input())
a = [int(i) for i in input().split(' ')]
ans = 0
(prefix, s) = ([0] * (n + 1), 0)
for i in range(n):
	s += a[i]
	prefix[i + 1] = s
(l, r) = (0, 0)
s = {0}
while l < n:
	while r < n and prefix[r + 1] not in s:
		r += 1
		s.add(prefix[r])
	ans += r - l
	s.remove(prefix[l])
	l += 1
print(ans)


from collections import defaultdict
n = int(input())
arr = list(map(int, input().split()))
arr = [-1] + arr
d = defaultdict(list)
d[0] = 0
(x, idx) = (0, 0)
cnt = 0
total = n * (n + 1) // 2
for i in range(1, n + 1):
	x += arr[i]
	if x in d and d[x] >= idx:
		cnt += (d[x] - idx + 1) * (n - i + 1)
		idx = d[x] + 1
	d[x] = i
print(total - cnt)


from sys import stdin
n = int(stdin.readline())
sm = 0
pre = {0: -1}
last_start = -1
ans = 0
for (i, a) in enumerate(map(int, stdin.readline().split())):
	sm += a
	if sm in pre:
		last_start = max(last_start, pre[sm] + 1)
	pre[sm] = i
	ans += i - last_start
print(ans)


from __future__ import print_function
from collections import Counter, OrderedDict
from itertools import permutations as perm
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
import math
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(n,) = gil()
a = gil()
(ans, store, end, pre) = (0, set([0]), 0, a[:])
for i in range(1, n):
	pre[i] += pre[i - 1]
pre.append(0)
for i in range(n):
	while end < n and pre[end] not in store:
		store.add(pre[end])
		end += 1
	ans += end - i
	store.remove(pre[i - 1])
print(ans)


n = int(input())
a = list(map(int, input().split()))
res = n * (n - 1) // 2 + n
last = {0: -1}
s = 0
j = -1
for i in range(n):
	s += a[i]
	if s in last and last[s] >= j:
		res -= (last[s] + 1 - j) * (n - i)
		j = last[s] + 1
	last[s] = i
print(res)


import sys
input = sys.stdin.buffer.readline
m = {}
n = int(input())
a = [int(x) for x in input().split()]
m[0] = 0
for i in range(1, n):
	a[i] += a[i - 1]
ans = 0
cur_max = -1
for i in range(n):
	val = m.get(a[i], -1)
	cur_max = max(cur_max, val)
	ans += i - cur_max
	m[a[i]] = i + 1
print(ans)


from collections import defaultdict
from sys import stdin
input = stdin.readline
n = int(input().strip())
a = [int(x) for x in input().strip().split()]
d = defaultdict(int)
d[0] = 1
start = 0
end = 0
ans = 0
cs = [0] * (n + 1)
while start < n and end < n:
	if a[end] == 0:
		start = end + 1
		end = start
		d = defaultdict(int)
	else:
		cs[end + 1] = cs[end] + a[end]
		if d[cs[end + 1]]:
			while d[cs[end + 1]]:
				d[cs[start]] -= 1
				start += 1
		else:
			ans += end - start + 1
			d[cs[end + 1]] += 1
			end += 1
print(ans)


from math import ceil, log2
from collections import defaultdict
from sys import stdin
from bisect import bisect_left as lower
input = stdin.readline

def read():
	return [int(i) for i in input().split()]
n = int(input())
l = list(read())
c = 0
p = [0]
for i in l:
	c += i
	p.append(c)
s = set()
i = 0
j = 1
s.add(0)
ans = 0
while i < n + 1:
	while j < n + 1 and p[j] not in s:
		s.add(p[j])
		j += 1
	ans += j - i - 1
	s.remove(p[i])
	i += 1
print(ans)


def I():
	return list(map(int, input().split()))

def sieve(n):
	a = [1] * n
	for i in range(2, n):
		if a[i]:
			for j in range(i * i, n, i):
				a[j] = 0
	return a
n = int(input())
arr = I()
l = -1
d = {0: -1}
prefix = [0] * (n + 1)
prefix[0] = arr[0]
ans = 0
for i in range(1, n):
	prefix[i] = arr[i] + prefix[i - 1]
for i in range(n):
	l = max(l, d.get(prefix[i], l - 1) + 1)
	d[prefix[i]] = i
	ans += i - l
print(ans)


n = int(input())
a = input().split()
a = [int(i) for i in a]
c = [0] * n
d = {}
A = 0
v1 = 0
d[0] = -1
idx = -1
for i in range(n):
	if i == 0:
		c[i] = a[i]
	else:
		c[i] = c[i - 1] + a[i]
	v = d.get(c[i])
	if v is not None:
		idx = max(idx, v + 1)
	if a[i] == 0:
		idx = max(idx, i)
	A += i - idx
	d[c[i]] = i
print(A)


import sys
from collections import defaultdict
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
res = 0
zis = [None] * n
d = defaultdict(int)
d[0] = -1
csum = 0
for (i, x) in enumerate(a):
	csum += x
	if csum in d:
		zis[i] = d[csum] + 1 if csum in d else -float('inf')
	d[csum] = i
left = 0
for i in range(n):
	if zis[i] is not None:
		left = max(left, zis[i] + 1)
	res += i - left + 1
print(res)