Kolya got an integer array $a_1, a_2, \dots, a_n$. The array can contain both positive and negative integers, but Kolya doesn't like $0$, so the array doesn't contain any zeros.

Kolya doesn't like that the sum of some subsegments of his array can be $0$. The subsegment is some consecutive segment of elements of the array. 

You have to help Kolya and change his array in such a way that it doesn't contain any subsegments with the sum $0$. To reach this goal, you can insert any integers between any pair of adjacent elements of the array (integers can be really any: positive, negative, $0$, any by absolute value, even such a huge that they can't be represented in most standard programming languages).

Your task is to find the minimum number of integers you have to insert into Kolya's array in such a way that the resulting array doesn't contain any subsegments with the sum $0$.


-----Input-----

The first line of the input contains one integer $n$ ($2 \le n \le 200\,000$) — the number of elements in Kolya's array.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^{9} \le a_i \le 10^{9}, a_i \neq 0$) — the description of Kolya's array.


-----Output-----

Print the minimum number of integers you have to insert into Kolya's array in such a way that the resulting array doesn't contain any subsegments with the sum $0$.


-----Examples-----
Input
4
1 -5 3 2

Output
1

Input
5
4 -2 3 -9 2

Output
0

Input
9
-1 1 -1 1 -1 1 1 -1 -1

Output
6

Input
8
16 -5 -11 -15 10 5 4 -4

Output
3



-----Note-----

Consider the first example. There is only one subsegment with the sum $0$. It starts in the second element and ends in the fourth element. It's enough to insert one element so the array doesn't contain any subsegments with the sum equal to zero. For example, it is possible to insert the integer $1$ between second and third elements of the array.

There are no subsegments having sum $0$ in the second example so you don't need to do anything.

Difficulty: introductory

Starter code:

Solutions:
from sys import stdin

tt = 1

for loop in range(tt):

    dic = {}
    dic[0] = 1

    n = int(stdin.readline())

    a = list(map(int,stdin.readline().split()))
    now = 0
    ans = 0

    for i in a:
        now += i
        if now in dic:
            ans += 1
            dic = {}
            dic[0] = 1
            now = i
            
        dic[now] = 1

    print (ans)

n = int(input())
arr = list(map(int, input().split()))

ans = 0
pref = [0]
prefset = {0}
for i in range(n):
    now = pref[-1] + arr[i]
    if now in prefset:
        ans += 1
        pref = [0, arr[i]]
        prefset = {0, arr[i]}
    else:
        pref.append(now)
        prefset.add(now)
    # print(pref)
    # print(prefset)

print(ans)


# Created by: WeirdBugsButOkay
# 28-09-2020, 13:52:29

import math

def solve() :
    n = int(input())
    a = list(map(int, input().split()))
    dict = {}
    dict[0] = 1
    sum, ans = 0, 0
    for i in range(0, n) :
        sum += a[i]
        #print(i, sum)
        if sum in list(dict.keys()) :
            ans += 1
            dict = {}
            dict[0] = 1
            sum = a[i]
            dict[sum] = 1
            #print("haha")
        else :
            dict[sum] = 1
    print(ans)
    

t = 1
#t = int(input())
for _ in range (0, t) :
    solve()


from sys import stdin, stdout

def find(arr,N):
    S=set([0])
    r=0
    k=0
    for i in arr:
        r+=i
        # print(S,r)
        if r in S: 
            k+=1
            S=set([0])
            r=i
        S.add(r)
    return k


def main():
    # for _ in range(int(stdin.readline())):
        N=int(stdin.readline())
        arr=list(map(int, stdin.readline().split()))
        print(find(arr,N))
main()

# for _ in range(int(input())):
for _ in range(1):
    n = int(input())
    arr = list(map(int, input().split()))
    d = dict()
    lst = -1
    ans = 0
    bal = 0
    d[0] = -1
    for i in range(n):
        nbal = bal + arr[i]
        if nbal in d:
            k = d[nbal]
            if k >= lst:
                ans += 1
                lst = i - 1
        bal = nbal
        d[bal] = i
    print(ans)


n=int(input())
l=input().split()
li=[int(i) for i in l]
hashi=dict()
pref=0
ans=0
hashi[pref]=1
for i in range(n):
    pref+=li[i]
    if(pref in hashi):
        ans+=1
        pref=li[i]
        hashi=dict()
        hashi[0]=1
        hashi[pref]=1
    else:
        hashi[pref]=1
print(ans)


import math
for _ in range(1):
    n=int(input())
    a=list(map(int,input().split()))
    ans=0
    s=0
    d={0:1}
    for i in range(n):
        s+=a[i]
        if s in d:
            ans+=1
            s=a[i]
            d={0:1}
            d[s]=1
        else:
            d[s]=1
    print(ans)        

n = int(input())
a = list(map(int,input().split()))

prefixes = set()
curr = 0
ans = 0
for i in range(n):
	curr += a[i]
	if curr==0 or curr in prefixes:
		ans += 1
		curr = a[i]
		prefixes.clear()
	prefixes.add(curr)

print(ans)

import sys
readline = sys.stdin.readline

N = int(readline())
A = list(map(int, readline().split()))

S = set([0])

cnt = 0
ans = 0
for a in A:
    cnt += a
    if cnt in S:
        ans += 1
        S = set([0, a])
        cnt = a
    else:
        S.add(cnt)
print(ans)

n = int(input())
lst = list(map(int,input().split()))
pref = dict()
sum = lst[0]
pref[lst[0]] = 1
pref[0] = 1
res = 0
for r in range(1, n):
    sum += lst[r]
    if pref.get(sum, 0):
        pref = dict()
        pref[0] = 1
        res += 1
        sum = lst[r]
    pref[sum] = 1
print(res)

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
done = {a[0]:0,0:0}
s = a[0]
ans = 0
for i in range(1,n):
	s += a[i]
	if s in done:
		done = {0:0,a[i]:0}
		ans += 1
		s = a[i]
	else:
		done[s] = 0
print (ans)


from itertools import accumulate
from collections import defaultdict

n = int(input())

a = list(map(int, input().split()))

acc = list(accumulate(a))

positions = defaultdict(lambda: [])

for i, val in enumerate(acc):
    positions[val].append(i)
    
intervals = []
    
for val, pos_list in list(positions.items()):
    if val == 0:
        intervals.append((pos_list[0], 0))
    for pos1, pos2 in zip(pos_list, pos_list[1:]):
        intervals.append((pos2, pos1+1))
        
intervals.sort()

ans = 0
prev = -10**10
for e, s in intervals:
    if s < prev:
        continue
    else:
        ans += 1
        prev = e
print(ans)


import sys
input = sys.stdin.readline

n=int(input())
A=list(map(int,input().split()))

S=[0]
for a in A:
    S.append(S[-1]+a)

ANS=0
SET=set()
for i in range(n+1):
    if S[i] in SET:
        ANS+=1
        SET={S[i],S[i-1]}
    else:
        SET.add(S[i])

print(ANS)




n = int(input())
a = list(map(int, input().split()))
m = {0}
ans = 0
summ = 0
for i in range(n):
    summ += a[i]
    if summ == 0 or summ in m:
        ans += 1
        m = {a[i]}
        summ = a[i]
    else:
        m.add(summ)
print(ans)


from bisect import *
from collections import *
from math import *
from heapq import *
from typing import List
from itertools import *
from operator import *
from functools import *
import sys
'''
@lru_cache(None)
def fact(x):
    if x<2:
        return 1
    return fact(x-1)*x

@lru_cache(None)
def per(i,j):
    return fact(i)//fact(i-j)

@lru_cache(None)
def com(i,j):
    return per(i,j)//fact(j)

def linc(f,t,l,r):
    while l<r:
        mid=(l+r)//2
        if t>f(mid):
            l=mid+1
        else:
            r=mid
    return l

def rinc(f,t,l,r):
    while l<r:
        mid=(l+r+1)//2
        if t<f(mid):
            r=mid-1
        else:
            l=mid
    return l

def ldec(f,t,l,r):
    while l<r:
        mid=(l+r)//2
        if t<f(mid):
            l=mid+1
        else:
            r=mid
    return l

def rdec(f,t,l,r):
    while l<r:
        mid=(l+r+1)//2
        if t>f(mid):
            r=mid-1
        else:
            l=mid
    return l

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

def power2(n):
    while not n&1:
        n>>=1
    return n==1
'''
'''
for i in range(t):
    #n,m=map(int,input().split())
    n,m=1,0
    graph=defaultdict(set)
    for i in range(m):
        u,v=map(int,input().split())
        graph[u-1].add(v-1)
    visited=[0]*n
    ans=[]
    def delchild(u):
        for child in graph[u]:
            visited[child]=1
            ans.append(child+1)
    for i in range(n):
        if not visited[i]:
            children=graph[i]
            if len(children)==1:
                u=children.pop()
                visited[u]=1
                delchild(u)
            elif len(children)==2:
                u=children.pop()
                v=children.pop()
                if u in graph[v]:
                    delchild(v)
                    visited[v]=1
                elif v in graph[u]:
                    delchild(u)
                    visited[u]=1
                else:
                    delchild(u)
                    delchild(v)
                    visited[u]=visited[v]=1
    print(len(ans))
    sys.stdout.flush()
    print(' '.join(map(str,ans)))
    sys.stdout.flush()

import time
s=time.time()
e=time.time()
print(e-s)
'''
'''
t=int(input())
for i in range(t):
    #n,m=map(int,input().split())
    n=int(input())
    x=int(sqrt(n))
    if x*x==n:
        ans=2*x-2
    elif x*(x+1)>=n:
        ans=2*x-1
    else:
        ans=2*x
    print(ans)
'''
n=int(input())
arr=list(map(int,input().split()))
d={0}
pre=0
ans=0
for a in arr:
    pre+=a
    if pre in d:
        ans+=1
        pre=a
        d={0,a}
    else:
        d.add(pre)
print(ans)
                
    



N, = list(map(int, input().split()))
X = list(map(int, input().split()))
#print(X)
for i in range(1, N):
    X[i] += X[i-1]
#print(X)
d = set([0])
R = 0
for i in range(N):
    if X[i] in d:
#        print(i)
        R += 1
        d = set()
    d.add(X[i])
    if i>0:
        d.add(X[i-1])
print(R)


from math import *
from sys import *
input = stdin.readline

for _ in range(1):
    
    n = int(input())
    a = list(map(int,input().split()))
    
    d = {0:1}
    cn = 0 
    
    sn = 0 
    for i in range(n):
        sn += a[i]
        if(d.get(sn,0) == 1):
            sn = a[i]
            cn += 1
            d = {0:1,a[i]:1}
        else:
            d[sn] = 1
    
    stdout.write(str(cn)+'\n')

input()

prefix_sums = set()
prefix_sums_shift = 1000
result = 0
for x in map(int, input().split()):
    if prefix_sums_shift - x in prefix_sums:
        result += 1
        prefix_sums = set()
        prefix_sums_shift = 0
    prefix_sums_shift -= x
    prefix_sums.add(x + prefix_sums_shift)
print(result)


n=int(input())
L=[0]
for i in map(int,input().split()):L.append(L[-1]+i)
d=dict()
ct=0
last=0
for i in L:
    if i not in d:d[i]=1
    else:
        ct+=1
        d=dict()
        d[last]=1
        d[i]=1
    last=i
print(ct)

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

from itertools import accumulate
from functools import lru_cache

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()

# l = list(accumulate(l))
d = {0:1}

currsum = ans = 0
for i in range(n):
    currsum += l[i]
    if currsum in d:
        d = {}
        d[0] = 1
        d[l[i]] = 1
        ans += 1
        currsum = l[i]
    else:d[currsum] = 1
    # print(currsum)
print(ans)

n = int(input())
A = [int(i) for i in input().split()]

cumm = [A[0]]*n
d = {A[0]: [0]}
count = 0
last_idx = -1
for i in range(1,n):
    cumm[i] = cumm[i-1]+A[i]

    if cumm[i] == 0 and last_idx == -1:
        # print(i)
        count += 1
        last_idx = i
    elif cumm[i] in d:
        l = d[cumm[i]]
        if l[-1] >= last_idx-1:
            # print(i, last_idx)
            count += 1
            last_idx = i

    if cumm[i] not in d:
        d[cumm[i]] = []
    d[cumm[i]].append(i)

print(count)


import sys,math
from collections import Counter,deque,defaultdict
from bisect import bisect_left,bisect_right 
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = inpl()
res = 0
now = 0
se = set()
for x in a:
    now += x 
    if now in se or now == 0:
        res += 1
        now = x
        se = set()
        se.add(now)
    else:
        se.add(now)
print(res)

def main():
    #n, m = map(int, input().split())
    n = int(input())
    a = list(map(int, input().split()))
    s = {0}
    acc = 0
    ans = 0
    for x in a:
        acc += x
        if acc in s:
            ans += 1
            s = {0, x}
            acc = x
        else:
            s.add(acc)
    print(ans)

#input = sys.stdin.readline

#sys.setrecursionlimit(2097152)
tn = 1 #int(input())
for _ in range(tn):
    main()