Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

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

count_l = [0] * n
for i in range(n):
    count_l[i] = d_l.count(i)

if d_l[0] != 0 or d_l.count(0) != 1:
    ans = 0
else:
    ans = 1

n_tmp = n-1
for i in range(1,n):
    ans = ans*(count_l[i-1]**count_l[i])%998244353
    n_tmp -= count_l[i]
    if n_tmp == 0:
        break

print(ans)

### FIXED CODE ###

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

count_dict = {}
for i in range(n):
    count_dict[i] = 0
for val in d_l:
    count_dict[val] += 1

if d_l[0] != 0 or count_dict[0] != 1:
    ans = 0
else:
    ans = 1

for i in range(1,n):
    ans = (ans*(count_dict[i-1]**count_dict[i])) %998244353
    if ans == 0:
        break

print(ans)
### BUGGY CODE ###

import collections

n = int(input())

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


l = [a[i] +i+1 for i in range(n)]
r = [i+1 -a[i] for i in range(n)]

L = collections.Counter(l)
R = collections.Counter(r)

c = 0

for i in range(max(max(l),max(r))+1):
    c += L.get(i, 0) * R.get(i, 0)

print(c)

### FIXED CODE ###

import collections

n = int(input())

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


l = [a[i] +i+1 for i in range(n)]
r = [i+1 -a[i] for i in range(n)]

L = collections.Counter(l)
R = collections.Counter(r)

c = 0

for i in L.keys():
    c += L.get(i, 0) * R.get(i, 0)

print(c)
### BUGGY CODE ###

N = int(input())
S = input()

num_r, num_g = S.count('R'), S.count('G')
num_b = N - num_r - num_g
max_ans = num_r * num_g * num_b
count_not_ans = 0
S = list(S)

for i in range(N-2):
    for j in range(i+1, N-1):
        k = 2 * j - i
        if (0 <= k <= N-1) and len(set([S[i], S[j], S[k]])) == 3:
            count_not_ans += 1

print(max_ans - count_not_ans)


### FIXED CODE ###

N = int(input())
S = input()

num_r, num_g = S.count('R'), S.count('G')
num_b = N - num_r - num_g
max_ans = num_r * num_g * num_b
count_not_ans = 0
S = list(S)

for i in range(N):
    for j in range(i+1, N):
        k = 2 * j - i
        if (0 <= k <= N-1) and len(set([S[i], S[j], S[k]])) == 3:
            count_not_ans += 1

print(max_ans - count_not_ans)
### BUGGY CODE ###

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

d = []
for i in range(m):
    b, c = map(int, input().split())
    d.extend([c]*b)

d.sort(reverse=True)

for i in range(min(n, len(d))):
    if a[i] >= d[i]:
        break
    a[i] = d[i]

print(sum(a))

### FIXED CODE ###

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

op = []
for i in range(m):
    b, c = map(int, input().split())
    op.append((c, b))

op.sort(reverse=True)

j = 0
k = 0

for i in range(n):
    if a[i] >= op[j][0]:
        break

    a[i] = op[j][0]
    k += 1

    if k >= op[j][1]:
        j += 1
        k = 0

    if j >= m:
        break

print(sum(a))
### BUGGY CODE ###

N,M = map(int, input().split())

L=[0]*M
R=[0]*M
for i in range(M):
  L[i], R[i] = map(int, input().split())

keys = []

for i in range(M):
  keys.append(range(L[i],R[i]+1))
  
gcount = 0
for j in range(1,N+1):
  count = 0
  for i in range(M):
    if j in keys[i]:
      count+=1
      
  if count == M:
    gcount +=1
    
print(gcount)

### FIXED CODE ###

N,M = map(int, input().split())

L=[0]*M
R=[0]*M
for i in range(M):
  L[i], R[i] = map(int, input().split())
    
print(max(min(R)-max(L)+1,0))
### BUGGY CODE ###

n = input()
S = list(map(int, input().split()))
q = input()
T = list(map(int, input().split()))
cnt = 0
for i in range(len(T)):
    if S.count(T[i]) >= 1:
        cnt += 1
print(cnt)

### FIXED CODE ###

_ = input()
S = set(input().split())
_ = input()
T = set(input().split())
print(len(S & T))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
def main():
    n=int(input())
    al=tuple(map(int,input().split()))
    arr=[0,0,0]
    for i in al:
        arr[i-1]+=1
    dp=[[[0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
    for c in range(n+1):
        for b in range(n+1):
            for a in range(n-b-c+1):
                if a==b==c==0:
                    continue
                if 0<=c-1<=n and 0<=b+1<=n:
                    dp[a][b][c]+=dp[a][b+1][c-1]*c/n
                if 0<=b-1<=n and 0<=a+1<=n:
                    dp[a][b][c]+=dp[a+1][b-1][c]*b/n
                if 0<=a-1<=n:
                    dp[a][b][c]+=dp[a-1][b][c]*a/n
                dp[a][b][c]=(dp[a][b][c]+1)*n/(a+b+c)
    print(dp[arr[0]][arr[1]][arr[2]])
if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
    n=int(input())
    al=tuple(map(int,input().split()))
    arr=[0,0,0]
    for i in al:
        arr[i-1]+=1
    dp=[[[0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
    for c in range(n+1):
        for b in range(n+1-c):
            for a in range(n-b-c+1):
                if a==b==c==0:
                    continue
                if 0<=c-1<=n and 0<=b+1<=n:
                    dp[a][b][c]+=dp[a][b+1][c-1]*c/n
                if 0<=b-1<=n and 0<=a+1<=n:
                    dp[a][b][c]+=dp[a+1][b-1][c]*b/n
                if 0<=a-1<=n:
                    dp[a][b][c]+=dp[a-1][b][c]*a/n
                dp[a][b][c]=(dp[a][b][c]+1)*n/(a+b+c)
    print(dp[arr[0]][arr[1]][arr[2]])
if __name__=='__main__':
    main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)


def dfs(i, j=-1):
    global g
    for k in g[i]:
        if k == j:
            continue

        ans[k] += ans[i]
        dfs(k, i)


n, q = map(int, input().split())

g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    g[a].append(b)
    g[b].append(a)

ans = [0]*n
for j in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x

dfs(0)
print(*ans)


### FIXED CODE ###

n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n-1)]
px = [list(map(int, input().split())) for _ in range(q)]

l = [[] for i in range(n+1)]
for a, b in ab:
    l[a].append(b)
    l[b].append(a)

value = [0 for i in range(n+1)]
for p, x in px:
    value[p] += x

s = [1]
flag = [False]*(n+1)
while s:
    v = s.pop()
    flag[v] = True
    for e in l[v]:
        if flag[e]:
            continue
        value[e] += value[v]
        s.append(e)

print(*value[1:])
### BUGGY CODE ###

from operator import lt
from functools import partial


def solve(string):
    n, *abc = map(int, string.split())
    a = sorted(abc[:n], reverse=True)
    b = sorted(abc[n:2 * n], reverse=True)
    c = sorted(abc[2 * n:], reverse=True)
    ab = [len(list(filter(partial(lt, _a), b))) for _a in a]
    bc = [0] + [len(list(filter(partial(lt, _b), c))) for _b in b]
    for i in range(1, len(bc)):
        bc[i] += bc[i - 1]
    return str(sum([bc[_ab] for _ab in ab]))


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(3)])))


### FIXED CODE ###

def solve(string):
    n, *abc = map(int, string.split())
    a = sorted(abc[:n], reverse=True)
    b = sorted(abc[n:2 * n], reverse=True)
    c = sorted(abc[2 * n:], reverse=True)
    ab = [0] * n
    j = 0
    for i, _a in enumerate(a):
        while j <= n - 1 and _a < b[j]:
            j += 1
        ab[i] = j
    bc = [0] * (n + 1)
    j = 0
    for i, _b in enumerate(b, start=1):
        while j <= n - 1 and _b < c[j]:
            j += 1
        bc[i] = j

    for i in range(1, len(bc)):
        bc[i] += bc[i - 1]
    return str(sum([bc[_ab] for _ab in ab]))


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(3)])))
### BUGGY CODE ###

import bisect
n = int(input())
l = sorted(list(map(int, input().split())))
count = 0
for i in range(n-1,-1,-1):
    for j in range(i-1,-1,-1):
        k = bisect.bisect_left(l[i+1::],l[i]+l[j])
        count += k
print(count)

### FIXED CODE ###

import bisect
n = int(input())
l = sorted(([int(x) for x in input().split()]))
count = 0
for i in range(n-1,-1,-1):
    for j in range(i-1,-1,-1):
        k = bisect.bisect_left(l,l[i]+l[j])
        count += k-(i+1)
print(count)
### BUGGY CODE ###

n,k,q = map(int,input().split())
a = [int(input()) for i in range(q)]
for i in range(n):
  if (k - q + a.count(i+1) > 0):
    print("Yes")
  else:
    print("No")


### FIXED CODE ###

from collections import Counter
n,k,q = map(int,input().split())
a = [int(input()) for i in range(q)]
c = Counter(a)
for i in range(n):
  if (k - q + c.get(i+1, 0) > 0):
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

def main():
    n = int(input())
    a_list = list(map(int, input().split()))

    a_dict = {}
    for a in a_list:
        if a not in a_dict:
            a_dict[a] = 1
        else:
            a_dict[a] += 1

    for k in range(n):
        cnt = 0
        a_dict[a_list[k]] -= 1
        for v in a_dict.values():
            if v >= 2:
                cnt += v * (v - 1) // 2
        a_dict[a_list[k]] += 1
        print(cnt)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    num_list = [0] * n  # 各番号が書かれたボールが何個あるか
    method_list = [0] * n  # 同じ番号が書かれた異なる2つのボールを選ぶ方法

    for a in a_list:
        num_list[a - 1] += 1

    for i in range(n):
        b = num_list[i]
        if b >= 2:
            method_list[i] = b * (b - 1) // 2

    total_method = sum(method_list)

    for k in range(n):
        c = a_list[k]  # k番目のボールに書かれている数字
        ans = total_method - method_list[c - 1]
        d = num_list[c - 1]
        if d >= 3:
            e = (d - 1) * (d - 2) // 2
        else:
            e = 0
        ans += e
        print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

import math
s = int(input())
r = 0
while s > r**2:
    r += 1
k = r**2 - s
def search_prime(k):
    p = math.floor(math.sqrt(k))
    for i in range(2,p + 1):
        if k % i == 0:
            return i
    return 1
prime = search_prime(k)
print("{} {} {} {} {} {}".format(0, 0, prime,r,r, int(k / prime)))

### FIXED CODE ###

import math
s = int(input())
r = math.floor(math.sqrt(s)) + 1
k = r**2 - s
if r == 10**9 + 1:
    print("{} {} {} {} {} {}".format(0, 0, 1,r - 1,r - 1, 0))
    exit()
def search_prime(k):
    p = math.floor(math.sqrt(k))
    for i in range(2,p + 1):
        if k % i == 0:
            return i
    return 1
prime = search_prime(k)
print("{} {} {} {} {} {}".format(0, 0, prime,r,r, int(k / prime)))
### BUGGY CODE ###

N=int(input())
A=map(int,input().split())
x=1
for a in A:
    x*=a

print(-1 if x>10**18 else x)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
x=1
for a in A:
    x*=a
    if x>10**18:
        print(-1)
        exit()

print(-1 if x>10**18 else x)
### BUGGY CODE ###

n = int(input())
a = [0] * n
 
for i in range(n):
    a[i] = int(input())
 
ct = 0
for i in range(n):
    t = a.count(a[i])
    if t % 2 == 1:  # nかかる？この時点でn^2?
        ct += 1
 
    i += t
 
print(ct)

### FIXED CODE ###

N = int(input())
ans = 0
n = []
for i in range(N):
  n.append(int(input()))
n.sort()
i=0
cnt = 1
while(i<N-1):
  if n[i] == n[i+1]:
    cnt+=1
  else:
    if cnt%2==1:
      ans+=1
    cnt = 1
    
  i+=1
if cnt%2==1:
  ans+=1

print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
a=1
if 0 in A:
    print(0)
else:
    for i in range(N):
        a=a*A[i]
    if a>(10**18):
        print('-1')
    else:
        print(a)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
a=1
if 0 in A:
    print(0)
else:
    for i in range(N):
        a*=A[i]
        if a>1000000000000000000:
          print(-1)
          break
    else:
        print(int(a))
### BUGGY CODE ###

N = int(input())
num = list(map(int,input().split()))
cnt = 0
flag = False
for i in range(N):
	for j in range(i):
		if num[i] > num[j]:
			flag = True
			break
	if(flag == False):
		cnt+=1
	flag = False
print(cnt)

### FIXED CODE ###

N = int(input())
num = list(map(int,input().split()))
cnt = 0
flag = False
num_min = 10**8
for i in range(N):
	if(i == 0):
		cnt+=1
		continue
	num_min = min(num_min,num[i-1])
	if (num[i] <= num_min):
		cnt+=1
print(cnt)
### BUGGY CODE ###

nm = input().split()
n = int(nm[0])
m = int(nm[1])
X = input().split()
Y = input().split()
X = map(int, X)
X = list(X)
Y = map(int, Y)
Y = list(Y)
S = 0
for i in range(n):
	for j in range(n - i):
		for k in range(m):
			for l in range(m - k):
				S += (X[i + j] - X[i]) * (Y[k + l] - Y[k])
ans = S % 1000000007
print(ans)

### FIXED CODE ###

#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, M = getlist()
	x = getlist()
	y = getlist()
	X = 0
	Y = 0
	for i in range(N - 1):
		X += ((x[i + 1] - x[i]) * (i + 1) * (N - i - 1)) % con
		X %= con
	for i in range(M - 1):
		Y += ((y[i + 1] - y[i]) * (i + 1) * (M - i - 1)) % con
		Y %= con
	print(X * Y % con)


if __name__ == '__main__':
	main()
### BUGGY CODE ###

N,K=map(int,input().split())
mod=10**9+7

import math
SQ=int(math.sqrt(N))

DP1=[1]*(SQ+1)
DP1[0]=0


DP2=[]

k=SQ

for i in range(SQ,0,-1):
    DP2.append(N//i-k)
    k=N//i

KOSUU2=[v for v in DP2]

for j in range(K-1):
    NDP1=[0]*(SQ+2)
    NDP2=[0]*(SQ+1)

    for j in range(1,SQ+1):
        NDP2[-j]-=DP1[j]
        NDP1[1]+=DP1[j]


    for j in range(-1,-SQ-1,-1):
        NDP1[-j+1]-=DP2[j]
        NDP1[1]+=DP2[j]

    for j in range(1,SQ+2):
        NDP1[j]=(NDP1[j]+NDP1[j-1])%mod

    NDP2[0]+=NDP1[-1]

    for j in range(1,SQ+1):
        NDP2[j]=(NDP2[j]+NDP2[j-1])%mod


    for j in range(SQ):
        NDP2[j]=NDP2[j]*KOSUU2[j]%mod

    DP1=NDP1
    DP2=NDP2
    DP1.pop()
    DP2.pop()

    
print((sum(DP1)+sum(DP2))%mod)

### FIXED CODE ###

N,K=map(int,input().split())
mod=10**9+7

import math
SQ=int(math.sqrt(N))

DP1=[1]*(SQ+1)
DP1[0]=0


DP2=[]

k=SQ

for i in range(SQ,0,-1):
    DP2.append(N//i-k)
    k=N//i


KOSUU2=[v for v in DP2]

#print(DP1)
#print(DP2)
#print()

for j in range(K-1):
    NDP1=[0]*(SQ+2)
    NDP2=[0]*(SQ+1)

    for j in range(1,SQ+1):
        NDP2[-j]-=DP1[j]
        NDP1[1]+=DP1[j]

    #print(NDP1)
    #print(NDP2)
    #print()

    for j in range(-1,-SQ-1,-1):
        NDP1[-j+1]-=DP2[j]
        NDP1[1]+=DP2[j]

    #print(NDP1)
    #print(NDP2)
    #print()

    for j in range(1,SQ+2):
        NDP1[j]+=NDP1[j-1]

    NDP2[0]+=NDP1[-1]

    for j in range(1,SQ+1):
        NDP2[j]+=NDP2[j-1]

    #print(NDP1)
    #print(NDP2)
    #print()

    for j in range(SQ):
        NDP2[j]=NDP2[j]*KOSUU2[j]

    #print(NDP1)
    #print(NDP2)
    #print()

    DP1=[n%mod for n in NDP1[:SQ+1]]
    DP2=[n%mod for n in NDP2[:SQ]]

    
print((sum(DP1)+sum(DP2))%mod)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
count=0
for i in range(1,n):
    j=0
    while True:
        if j+i>n-1:
            break
        if a[j]+a[j+i]==i:
            count+=1
        j+=1
print(count)

### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
jc=[0]*n
for i in range(n):
    jc[i]+=i+1-a[i]
jcc=Counter(jc)
count=0
for j in range(n):
    count+=jcc[a[j]+j+1]
print(count)
### BUGGY CODE ###

from scipy.sparse.csgraph import dijkstra
from scipy.sparse.csgraph import floyd_warshall
n=int(input())
g=[[float('inf') for i in range(n)]for j in range(n)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    g[a-1][b-1]=c
q,k=map(int,input().split())
k-=1
cost=dijkstra(g,unweighted=False,directed=False)
for i in range(q):
    a,b=map(int,input().split())
    print(int(cost[a-1][k]+cost[k][b-1]))


### FIXED CODE ###

n=int(input())
ro=[{}for i in range(n)]
dis=[-1]*n
for i in range(n-1):
    a,b,c=map(int,input().split())
    ro[a-1][b-1]=c
    ro[b-1][a-1]=c
q,k=map(int,input().split())
dis[k-1]=0
stack=[k-1]
while stack:
    s=stack.pop()
    for i,j in ro[s].items():
        if dis[i] == -1:
            dis[i]=dis[s]+j
            stack.append(i)
for i in range(q):
    x,y=map(int,input().split())
    x,y=x-1,y-1
    print(dis[x]+dis[y])
### BUGGY CODE ###

def main():
    H, W = [int(s) for s in input().split()]
    sh, sw = [int(s) -1 for s in input().split()]
    gh, gw = [int(s) -1 for s in input().split()]
    maze = []
    for i in range(H):
        maze.append(input())
    queue = [(sh, sw)]
    skip = 0
    seen = {(sh, sw)}
    nqs = set()
    while queue:
        nq = []
        while queue:
            x, y = queue.pop()
            if x == gh and gw == y:
                print(skip)
                return
            for i,j in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                if 0 <= i+x < H and 0 <= j+y < W:
                    ns = (i+x, j+y)
                    if maze[i+x][j+y] == '.':
                        if ns in seen:
                            continue
                        seen.add(ns)
                        queue.append(ns)
            ns = (x,y)
            if ns not in nqs:
                nqs.add(ns)
                nq.append(ns)

        skip += 1
        queue = []
        for x, y in nq:
            for i in range(-2, 3):
                for j in range(-2, 3):
                    if 0 <= i+x < H and 0 <= j+y < W:
                        if maze[i+x][j+y] == '.':
                            ns = (i+x, j+y)
                            if ns not in seen:
                                seen.add(ns)
                                queue.append(ns)
        # print(queue)
    print(-1)

main()

### FIXED CODE ###

def main():
    H, W = [int(s) for s in input().split()]
    sh, sw = [int(s) -1 for s in input().split()]
    gh, gw = [int(s) -1 for s in input().split()]
    maze = []
    for i in range(H):
        maze.append(input())
    queue = [(sh, sw)]
    skip = 0
    seen = {(sh, sw)}
    nqs = set()
    while queue:
        nq = []
        while queue:
            x, y = queue.pop()
            if x == gh and gw == y:
                print(skip)
                return
            for i,j in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                if 0 <= i+x < H and 0 <= j+y < W:
                    ns = (i+x, j+y)
                    if maze[i+x][j+y] == '.':
                        if ns in seen:
                            continue
                        seen.add(ns)
                        queue.append(ns)
            ns = (x,y)
            if ns not in nqs:
                nqs.add(ns)
                nq.append(ns)

        skip += 1
        queue = []
        for x, y in nq:
            for i in range(-2, 3):
                for j in range(-2, 3):
                    if 0 <= i+x < H and 0 <= j+y < W:
                        if maze[i+x][j+y] == '.':
                            ns = (i+x, j+y)
                            if ns not in seen:
                                seen.add(ns)
                                queue.append(ns)
        # print(queue)
    print(-1)

main()
### BUGGY CODE ###

from heapq import heappush, heappop

infi = 10 ** 20
n, m, s = map(int, input().split())
time_graph = [[] for _ in range(n + 1)]
money_graph = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    time_graph[v].append((b, u))
    time_graph[u].append((b, v))
    money_graph[u][v] = a
    money_graph[v][u] = a


rate = [(0, 0) for _ in range(n + 1)]
for i in range(1, n + 1):
    c, d = map(int, input().split())
    rate[i] = (c, d)

start = 1

time = [infi] * (n + 1)
time[start] = 0
que = [(0, s, start)]
cnt = 0
visited = set()
cnt = 0
while que:
    t_edge, m_edge, edge = heappop(que)
    if time[edge] > t_edge:
        time[edge] = t_edge
    if not (edge in visited):
        cnt += 1
        visited.add(edge)
    if cnt == n:
        break
    delta_money, delta_time = rate[edge]
    heappush(que, (t_edge + delta_time, m_edge + delta_money, edge))
    for t_newedge, newedge in time_graph[edge]:
        newtime = t_edge + t_newedge
        newmoney = m_edge - money_graph[edge][newedge]
        if newmoney < 0:
            continue
        heappush(que, (newtime, newmoney, newedge))

print(*time[2:], sep="\n")


### FIXED CODE ###

from heapq import heappush, heappop

infi = 10 ** 20
n, m, s = map(int, input().split())

s = min(s, 2500)

edges = [[] for _ in range(51 * 2501 + 1)]
# edge:1-50, max silver=0-2500

for _ in range(m):
    u, v, a, b = map(int, input().split())
    for i in range(a, 2501):
        edges[v + 50 * i].append((b, u + 50 * (i - a)))
        edges[u + 50 * i].append((b, v + 50 * (i - a)))


for edge_num in range(1, n + 1):
    c, d = map(int, input().split())
    # c枚, d分
    for i in range(2501):
        # 点edge_num+ i * 50のところに
        if edge_num + (i + c) * 50 <= 51 * 2501:
            edges[edge_num + i * 50].append((d, edge_num + min((i + c), 2500) * 50))
start = 1 + 50 * s


def dijkstra(edges, start):
    time = [infi] * (51 * 2501 + 1)
    used = [False] * (51 * 2501 + 1)
    # time[i][j] 頂点i, 銀貨jのときの時間
    time[start] = 0
    edgelist = []
    heappush(edgelist, (0, start))
    while edgelist:
        nowtime, nowedge = heappop(edgelist)
        if used[nowedge] is True:
            continue
        used[nowedge] = True
        time[nowedge] = nowtime
        for vt, v in edges[nowedge]:
            if used[v] is True:
                continue
            newtime = nowtime + vt
            heappush(edgelist, (newtime, v))
    return time


time = dijkstra(edges, start)

ans = [infi] * (51)
for i in range(1, 51 * 2501 + 1):
    temp = time[i]
    a = i % 50
    if a == 0:
        a += 50
    ans[a] = min(temp, ans[a])

print(*ans[2 : (n + 1)], sep="\n")
### BUGGY CODE ###

#AGC023 A
'''
問題
長さNの整数列Aがある
Nは1以上20000以下
Aiは-10**9以上10**9以下
Aの空でない連続する部分列であって，その総和が0であるものの個数は？

考察
区間[i,j]を取り出して0になるかどうかを試す
これを0<=i<=j<=20000について繰り返す
計算時間はO(N**2)
つまりループ回数が10**10になる->大丈夫?
'''

N = int(input())
A = list(map(int,input().split(' ')))

ans = 0

for i in range(N):
	for j in range(i,N):
		if sum(A[i:(j+1)]) == 0:
			ans += 1
		else:
			continue
			
print(ans)

### FIXED CODE ###

#AGC023 A: 部分和は先頭からの

#AGC023 A
'''
問題
長さNの整数列Aがある
Nは1以上20000以下
Aiは-10**9以上10**9以下
Aの空でない連続する部分列であって，その総和が0であるものの個数は？

考察1
区間[i,j]を取り出して0になるかどうかを試す
これを0<=i<=j<=20000について繰り返す
計算時間はO(N**2)
つまりループ回数が10**10になる->大丈夫?
-> 大丈夫ではない。予想通りTLEになった

考察2
思いつかない...

解説を読んでやり直し
S0 = 0
S1 = A1
S2 = A1 + A2
...
Si = A1 + ... + Ai
とすると, 0<=p<q<=Nとなる(p,q)を選んでSq-Spを計算することによって任意の部分和を構成できる
Sq-Sp=0であればA_(p+1) + ... + Aqの部分和が0である
したがって0<=p<q<=Nとなる(p,q)に対してSp=Sqとなる(p,q)の組を数えればよい
このためにはS0,S1,...をソートして
Siをソートするところがボトルネックとなり, 計算量はO(NlogN)
'''

'''
#考察1は失敗
N = int(input())
A = list(map(int,input().split(' ')))

ans = 0

for i in range(N):
	for j in range(i,N):
		if sum(A[i:(j+1)]) == 0:
			ans += 1
		else:
			continue
			
print(ans)
'''

N = int(input())
A = list(map(int,input().split(' ')))
S = [0]
Scount = [1]
ans = 0

for i in range(N):
	#print(A[0:i+1])
	#S.append(sum(A[0:i+1])) <- これは遅くなるのでNG
	S.append(S[-1]+A[i])
	#print(S)

S = sorted(S)

#for s in list(dict.fromkeys(S)):
	#Scount.append(S.count(s)) <- これも遅くなるのでNG
	
for i in range(N+1):
	if i==0:
		continue
	elif S[i]==S[i-1]:
		Scount[-1] += 1
	else:
		Scount.append(1)

for n in Scount:
	ans += (n*(n-1)/2)

print(int(ans))