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

#!/usr/bin/env python3
import sys
INF = 1<<32

def solve(N: int, K: int, h: "List[int]"):
    dp = [INF] * (N+2)
    dp[0] = 0
    dp[1] = abs(h[1]-h[0])

    for i in range(N):
        for j in range(1, K+1):
            if(i+j < N):
                dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))
            # if(i+1 < N):
            #     dp[i+1] = min(dp[i+1], dp[i]+abs(h[i+1]-h[i]))
            # if(i+2 < N):
            #     dp[i+2] = min(dp[i+2], dp[i]+abs(h[i+2]-h[i]))

    print(dp[N-1])
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    h = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, h)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, K: int, h: "List[int]"):
    INF = 10000000000
    dp = [INF]* (N+1)
    dp[0] = 0
    dp[1] = abs(h[1]-h[0])
    for i in range(2,N):
        for t in range(1,K+1):
            if(i-t >= 0):
                dp[i] = min(dp[i], dp[i-t]+abs(h[i]-h[i-t]))
        # print(dp)
    print(dp[N-1])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    h = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, K, h)

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

import collections
 
# A = input()
# A = int(input())
# A = map(int, input().split())
# A = list(map(int, input().split()))
# A = [int(input()) for i in range(N)]
#
# c = collections.Counter()
 
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [tuple(map(int, input().split())) for i in range(M)]
 
cl = collections.Counter(A)
for key in cl:
  BC.append((cl[key], key))

BC = sorted(BC, key=lambda x: -x[1])
 
c = 0
total = 0
for (n, key) in BC:
  for i in range(n):
    if c < N:
      c += 1
      total += key

print(total)

### FIXED CODE ###

import collections
 
# A = input()
# A = int(input())
# A = map(int, input().split())
# A = list(map(int, input().split()))
# A = [int(input()) for i in range(N)]
#
# c = collections.Counter()
 
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [tuple(map(int, input().split())) for i in range(M)]
 
cl = collections.Counter(A)
BC += [(cl[key], key) for key in cl]
BC = sorted(BC, key=lambda x: -x[1])
 
c = 0
total = 0
for (n, key) in BC:
  if (c + n) < N:
    c += n
    total += key * n
  else:
    total += key * (N - c)
    break

print(total)
### BUGGY CODE ###

N, W = [int(i) for i in input().split()]
weight = [0]
value = [0]
for _ in range(N):
    temp1, temp2 = [int(i) for i in input().split()]
    weight.append(temp1)
    value.append(temp2)

dp = [[0] * (W + 1) for N in range(N + 1)]
#%%
for i in range(1, N + 1):
    for j in range(1, W + 1):
        if weight[i] <= j:
            dp[i][j] = max(value[i] + dp[i - 1][j - weight[i]] , dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]

print(dp[N][W])


### FIXED CODE ###

N, W = [int(i) for i in input().split()]
weight, value = [0] * (N + 1), [0] * (N + 1)
for i in range(1, N + 1):
    weight[i], value[i] = [int(i) for i in input().split()]
#%%
dp = [[0] * (W + 1) for _ in range(N + 1)]

#%%
for i in range(1, N + 1):
    for j in range(1, W + 1):
        if weight[i] <= j:
            dp[i][j] = max(value[i] + dp[i - 1][j - weight[i]], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]
print(int(dp[-1][-1]))
### BUGGY CODE ###

N = int(input())
src = list(map(int,input().split()))

def enough(n):
    bit = [0] * (2*N+10)
    def bit_add(a,w):
        x = a
        while x <= (2*N+9):
            bit[x] += w
            x += (x & -x)
    def bit_sum(a):
        x = a
        ret = 0
        while x > 0:
            ret += bit[x]
            x -= (x & -x)
        return ret

    cums = [0]
    for a in src:
        tmp = 1 if a >= n else -1
        cums.append(cums[-1] + tmp)

    cnt = 0
    for i in range(N+1):
        a = cums[i] + N+5
        cnt += bit_sum(a)
        bit_add(a, 1)
    return cnt*2 >= N*(N+1)//2

ok = 0
ng = 10**9+1
while ng - ok > 1:
    m = (ok+ng)//2
    if enough(m):
        ok = m
    else:
        ng = m
print(ok)

### FIXED CODE ###

N = int(input())
src = list(map(int,input().split()))

cands = list(sorted(set(src)))

def enough(i):
    bit = [0] * (2*N+10)
    def bit_add(a,w):
        x = a
        while x <= (2*N+9):
            bit[x] += w
            x += (x & -x)
    def bit_sum(a):
        x = a
        ret = 0
        while x > 0:
            ret += bit[x]
            x -= (x & -x)
        return ret

    cums = [0]
    for a in src:
        tmp = 1 if a >= cands[i] else -1
        cums.append(cums[-1] + tmp)

    cnt = 0
    for i in range(N+1):
        a = cums[i] + N+5
        cnt += bit_sum(a)
        bit_add(a, 1)
    return cnt*2 >= N*(N+1)//2

ok = 0
ng = len(cands)
while ng - ok > 1:
    m = (ok+ng)//2
    if enough(m):
        ok = m
    else:
        ng = m
print(cands[ok])
### BUGGY CODE ###

H,W=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
B=[list(map(int,input().split())) for i in range(H)]
d=[[set() for i in range(W+1)] for j in range(H+1)]
d[1][1].add(A[0][0]-B[0][0])
d[1][1].add(B[0][0]-A[0][0])
for h in range(H):
    for w in range(W):
        x=A[h][w]-B[h][w]
        for y in d[h][w+1]:
            d[h+1][w+1].add((y+x)%(80*H*W))
            d[h+1][w+1].add((y-x)%(80*H*W))
        for y in d[h+1][w]:
            d[h+1][w+1].add((y+x)%(80*H*W))
            d[h+1][w+1].add((y-x)%(80*H*W))
for i in range(80*H*W):
    if i in d[H][W] or -i in d[H][W]:
        print(i)
        exit()

### FIXED CODE ###

H,W=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
B=[list(map(int,input().split())) for i in range(H)]
d=[[0]*W for j in range(H)]
m=80*(H+W)
d[0][0]=1<<m
for h in range(H):
    for w in range(W):
        x=abs(A[h][w]-B[h][w])
        if h>0:
            d[h][w]|=d[h-1][w]
        if w>0:
            d[h][w]|=d[h][w-1]
        d[h][w]=d[h][w]<<x|d[h][w]>>x
x,y=1<<m,1<<m
for i in range(99):
    if d[H-1][W-1]&x or d[H-1][W-1]&y:
        print(i)
        exit()
    x<<=1
    y>>=1
### BUGGY CODE ###

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

R_num=S.count('R')
G_num=S.count('G')
B_num=S.count('B')

ans=0
for k in range(N//2-2+1 if N&1==0 else N//2-1+1):
    flag=0
    for i in range(N-k-2):

        if i+2*(k+1)<=N-1:
            ls=[S[i],S[i+k+1],S[i+2*(k+1)]]
    
            if "R" in ls and "G" in ls and "B" in ls:
                ans+=1


print(R_num*G_num*B_num-ans)

### FIXED CODE ###

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

R_num=S.count('R')
G_num=S.count('G')
B_num=S.count('B')

ans=0
for k in range(N//2-2+1 if N&1==0 else N//2-1+1):
    flag=0
    for i in range(N-k-2):

        if i+2*(k+1)<=N-1:
            ls=[S[i],S[i+k+1],S[i+2*(k+1)]]
    
            if "R" in ls and "G" in ls and "B" in ls:
                ans+=1


print(R_num*G_num*B_num-ans)
### BUGGY CODE ###

import sys
def main():
    input=sys.stdin.readline
    N,K=map(int,input().split())
    H=list(map(int,input().split()))
    if N-1<=K:
        print(H[N-1]-H[0])
        return
    inf=10**9+7
    dp=[inf]*N
    dp[0]=0

    for i,h in enumerate(H):
        if i==0:continue
        m=inf
        M=max(0,i-K)
        for ht,dpt in zip(H[M:i],dp[M:i]):
            m=min(m, dpt+abs(h-ht))
        dp[i]=m
    print(dp[N-1])
    return
if __name__=="__main__":
    main()

### FIXED CODE ###

import sys
def main():
    input=sys.stdin.readline
    N,K=map(int,input().split())
    H=tuple(map(int,input().split()))
    if N-1<=K:
        print(H[N-1]-H[0])
        return
    inf=10**9+7
    dp=[inf]*N
    dp[0]=0

    for i,h in enumerate(H[1:]):
        m=inf
        for j in range(max(0,i-K+1), i+1):
            m=min(m, dp[j]+abs(h-H[j]))
        dp[i+1]=m
    print(dp[N-1])

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

N = int(input())
A = [int(_) for _ in input().split()]

B = []
for i in range(1, N+1)[::-1]:
    a = A[i-1]
    v = len(list(filter(lambda x: x % i == 0, B)))
    if v % 2 != a:
        B.append(i)

for i in range(1, N+1)[::-1]:
    a = A[i-1]
    v = len(list(filter(lambda x: x % i == 0, B)))
    if v % 2 != a:
        print(-1)
        exit(0)

print(len(B))
if B != []:
    print(" ".join([str(b) for b in B]))
    

### FIXED CODE ###

N = int(input())
A = [int(_) for _ in input().split()]

X = [0 for _ in range(N)]
ans = []
for i in range(N)[::-1]:
    v = 0
    for j in range(i, N, i+1):
        v += X[j]
    if v % 2 != A[i]:
        X[i] = 1
        ans.append(i+1)

print(len(ans))
for i in ans:
    print(i)
### BUGGY CODE ###

s = input()
k = int(input())
word = []
for i in range(len(s)):
  for j in range(i+1, len(s)+1):
    word.append(s[i:j])
word = sorted(list(set(word)))
print(word[k-1])

### FIXED CODE ###

s = input()
k = int(input())
word = []
for i in range(len(s)):
  for j in range(i+1, i+k+1):
    word.append(s[i:j])
word = sorted(list(set(word)))
print(word[k-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0]*n
for i in a:
    b[i-1] = a.index(i)+1
print(*b)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0]*n
for i in range(n):
    b[a[i]-1] = i+1
print(*b)
### BUGGY CODE ###

import sys

n = int(input())
d = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))

d.sort()

def solve(num,s,l):
	if s == l:
		if d[s] == num:
			return s
		else:
			return -1
	elif s+1 == l:
		if d[s] == num:
			return s
		elif d[l] == num:
			return l
		else:
			return -1

	c = s + (l-s)//2
	if d[c] == num:
		return c
	elif d[c] < num:
		return solve(num,c,l)
	else:
		return solve(num,s,c)

for i in range(m):
	A = solve(t[i],0,n-1)
	if A == -1:
		print("NO")
		sys.exit()
	else:
		d.pop(A)
		n -= 1

print("YES")

### FIXED CODE ###

import sys
import collections as c
n = int(input())
d = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))

D = c.Counter(d)
T = c.Counter(t)

for test in T.keys():
	if D[test] >= T[test]:
		continue
	else:
		print("NO")
		sys.exit()

print("YES")
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
ctr = 0
while 1:
    od = 0
    for i in range(N):
        if a[i]%2 == 0:
            a[i] /= 2
            ctr += 1
            break
        else:
            od += 1
    if od == N:
        break
print(ctr)

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
ctr = 0
for i in range(N):
    n = a[i]
    while a[i]%2 == 0:
        a[i] = a[i]/2
        ctr+=1
print(ctr)
### BUGGY CODE ###

N,X,Y = map(int,input().split())
for k in range(1,N):
    S = 0
    for i in range(1,N):
        for j in range(i+1,N+1):
            if min(j-i,abs(X-i)+abs(Y-j)+1,abs(X-j)+abs(Y-i)+1) == k:
                S += 1
    print(S)

### FIXED CODE ###

N,X,Y = map(int,input().split())
A = [0 for i in range(N)]
for i in range(N-1):
    a = i+1
    for j in range(i+1,N):
        b = j+1
        A[min([b-a,abs(X-a)+abs(Y-b)+1])] += 1
for i in range(1,N):
    print(A[i])
### BUGGY CODE ###

n, m = map(int, input().split())
a=[]
for i in range(m):
    a.append(int(input()))

r=[0]*(n+1)
r[0]=1

for i in range(1,n+1):
    if i in a:
        continue
    r[i]=(r[i-1]+r[i-2])%1000000007

print(r[n])

### FIXED CODE ###

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

a=[True]*(n+1)
for i in range(m):
    a[int(input())]=False

r=[0]*(n+1)
r[0]=1

for i in range(1,n+1):
    if not a[i]:
        continue
    r[i]=(r[i-1]+r[i-2])%1000000007

print(r[n])
### BUGGY CODE ###

N,M=map(int,input().split())
box=[]
A=list(map(int,input().split()))
for _ in range(M):
  b,c=map(int,input().split())
  for __ in range(b):
    A.append(c)
A.sort()
A.reverse()
print(sum(A[:N]))

### FIXED CODE ###

N,M=map(int,input().split())
box=[]
A=list(map(int,input().split()))
for i in A:
  box.append((i,1))
for _ in range(M):
  b,c=map(int,input().split())
  box.append((c,b))
box = sorted(box, key=lambda x:x[0])
box.reverse()
ans=0
count=0
for i in range(0,10**5):
  ans+=(box[i][0]*box[i][1])
  count+=box[i][1]
  if count >N:
    ans-=((count-N)*box[i][0])
    break
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
Q_list = [input().split() for i in range(Q)]

for tmp_Q in Q_list:
    if len(tmp_Q) == 1:
        S = S[::-1]
    else:
        if tmp_Q[1] == "1":
            S = tmp_Q[2] + S
        else:
            S = S + tmp_Q[2]

print(S)

### FIXED CODE ###

S = input()
Q = int(input())

is_reversed = False
head = ""

for i in range(Q):
    tmp_Q = input().split()

    if len(tmp_Q) == 1:
        is_reversed = not is_reversed
        
    else:
        if tmp_Q[1] == "1":
            if is_reversed:
                S = S + tmp_Q[2]
            else:
                head = head + tmp_Q[2]
        else:
            if is_reversed:
                head = head + tmp_Q[2]
            else:
                S = S + tmp_Q[2]

if is_reversed:
    print(S[::-1] + head)
else:
    print(head[::-1] + S)
### BUGGY CODE ###

k,s = map(int,input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                ans += 1
print(ans)

### FIXED CODE ###

k,s = map(int,input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0 <= z <= k:
            ans += 1
print(ans)
### BUGGY CODE ###

import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離

s = input()
t = input()
sl = len(s)
tl = len(t)

dp = [[0 for _ in range(tl+1)] for _ in range(sl+1)]

for i in range(sl):
    for j in range(tl):
        if s[i] == t[j]: dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])

ans = ''
while sl > 0 and tl > 0:
    if dp[sl][tl] == dp[sl][tl-1]:
        tl -= 1
    elif dp[sl][tl] == dp[sl-1][tl]:
        sl -= 1
    else:
        ans = s[sl-1] + ans
        sl -= 1
        tl -= 1
print(ans)




### FIXED CODE ###

import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離

s = input()
t = input()
sl = len(s)
tl = len(t)

dp = [[0 for _ in range(tl+1)] for _ in range(sl+1)]

for i in range(sl):
    for j in range(tl):
        if s[i] == t[j]: dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])

ans = ''
while sl > 0 and tl > 0:
    if dp[sl][tl] == dp[sl][tl-1]:
        tl -= 1
    elif dp[sl][tl] == dp[sl-1][tl]:
        sl -= 1
    else:
        ans = s[sl-1] + ans
        sl -= 1
        tl -= 1
print(ans)
### BUGGY CODE ###

from scipy.misc import comb

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

K = {}
for row in A:
    if row in K:
      K[row] += 1
    else:
      K[row] = 1

# 辞書Kに関して全探索
for row in A:
    ans = 0
    for i in K:
        if i == row:
            ans += comb(K[i]-1,2,exact=True)
        else:
            ans += comb(K[i],2,exact=True)
    print(int(ans))


### FIXED CODE ###

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

K = {}
for row in A:
  if row in K:
    K[row] += 1
  else:
    K[row] = 1
        
# 最大数を計算
max = 0
for i in K:
  max += int(K[i]*(K[i]-1)/2)

# 辞書Kに関して全探索
for i in A:
  print(max - int(K[i]*(K[i]-1)/2) + int((K[i]-1)*(K[i]-2)/2) )
### BUGGY CODE ###

s = input()
ans = 0
flg = 0
while '10' in s or '01' in s:
    ans += s.count('01') * 2
    s = s.replace('01', '')
    ans += s.count('10') * 2
    s = s.replace('10', '')
print(ans)

### FIXED CODE ###

s = input()
print(min(s.count('1'),s.count('0')) * 2)
### BUGGY CODE ###

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

ans = 1
for a in A:
    ans *= a
print(ans if ans <= 10**18 else -1)

### FIXED CODE ###

import sys
N = int(input())
A = sorted(list(map(int, input().split())))

if 0 in A:
    print(0)
    sys.exit()

ans = 1
for a in A:
    ans *= a
    if ans > 10**18:
        print(-1)
        sys.exit()
else:
    print(ans)
### BUGGY CODE ###

N = int(input())

A = list(map(int, input().split()))
AList = [bin(i) for i in A]
AList = [int(i, 2) for i in AList]
count = 0
for i in range(0, N):
    for q in range(i, N):
        count += int(bin(AList[i] ^ AList[q]), 2)
print(count % (10 ** 9 + 7))

### FIXED CODE ###

import numpy as np

mod = 10 ** 9 + 7

N = int(input())
 
AList = np.array(input().split(), dtype=np.int64)
count = 0
for i in range(60):
    Plus = np.count_nonzero(AList >> i & 1)
    count += 2 ** i * (Plus * (N - Plus))
print(count % mod)
### BUGGY CODE ###

from collections import deque
import sys
imput = sys.stdin.readline


diff = ((0, 1), (0, -1), (1, 0), (-1, 0))
n = int(input())
p = list(map(int, input().split()))

cost = [0] * (n * n)
for i in range(n):
    for j in range(n):
        cost[i * n + j] = min(i, j, n - i - 1, n - j - 1)

occ = [True] * (n * n)
ans = 0
for start in p:
    start -= 1
    q = deque([start])
    ans += cost[start]
    occ[start] = False
    while q:
        ij = q.popleft()
        i, j = divmod(ij, n)
        for di, dj in diff:
            nxt_i = i + di
            nxt_j = j + dj
            nxt_ij = nxt_i * n + nxt_j
            if not(0 <= nxt_i < n and 0 <= nxt_j < n):
                continue
            if not occ[ij]:
                if cost[nxt_ij] > cost[ij]:
                    cost[nxt_ij] = cost[ij]
                    q.append(nxt_ij)
            else:
                if cost[nxt_ij] > cost[ij] + 1:
                    cost[nxt_ij] = cost[ij] + 1
                    q.append(nxt_ij)

print(ans)

### FIXED CODE ###

from collections import deque
import sys
imput = sys.stdin.readline


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

cost = [0] * (n * n)
for i in range(n):
    for j in range(n):
        cost[i * n + j] = min(i, j, n - i - 1, n - j - 1)

occ = [True] * (n * n)
ans = 0
for start in p:
    start -= 1
    q = deque([start])
    ans += cost[start]
    occ[start] = False
    while q:
        ij = q.popleft()
        i, j = divmod(ij, n)

        nxt_ij = (i + 1) * n + j
        if not(0 <= i + 1 < n and 0 <= j < n):
             pass
        elif not occ[ij] and cost[nxt_ij] > cost[ij]:
            cost[nxt_ij] = cost[ij]
            q.append(nxt_ij)
        elif cost[nxt_ij] > cost[ij] + 1:
            cost[nxt_ij] = cost[ij] + 1
            q.append(nxt_ij)
              
        nxt_ij = (i - 1) * n + j
        if not(0 <= i - 1 < n and 0 <= j < n):
            pass
        elif not occ[ij] and cost[nxt_ij] > cost[ij]:
            cost[nxt_ij] = cost[ij]
            q.append(nxt_ij)
        elif cost[nxt_ij] > cost[ij] + 1:
            cost[nxt_ij] = cost[ij] + 1
            q.append(nxt_ij)

        nxt_ij = i * n + (j + 1)
        if not(0 <= i + 0 < n and 0 <= j + 1 < n):
            pass
        elif not occ[ij] and cost[nxt_ij] > cost[ij]:
            cost[nxt_ij] = cost[ij]
            q.append(nxt_ij)
        elif cost[nxt_ij] > cost[ij] + 1:
            cost[nxt_ij] = cost[ij] + 1
            q.append(nxt_ij)

        nxt_ij = i * n + (j - 1)
        if not(0 <= i < n and 0 <= j - 1 < n):
            pass
        elif not occ[ij] and cost[nxt_ij] > cost[ij]:
            cost[nxt_ij] = cost[ij]
            q.append(nxt_ij)
        elif cost[nxt_ij] > cost[ij] + 1:
            cost[nxt_ij] = cost[ij] + 1
            q.append(nxt_ij)
print(ans)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
a = LIST()
arr = [0 for _ in range(n + 1)]
arr[1] = a[0]
for i in range(1, n):
    arr[i + 1] = arr[i] + a[i]
setarr = set(arr)
countarr = Counter(arr)
ans = 0
for i in range(n):
    s = arr[i]
    if s in setarr:
        ans += Counter(arr[i + 1:])[s]
print(ans)

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
a = LIST()
arr = [0 for _ in range(n + 1)]
arr[1] = a[0]
for i in range(2, n + 1):
    arr[i] = arr[i - 1] + a[i - 1]
arr2= Counter(arr)
arr3 = list(set(arr))
ans = 0
for i in range(len(arr3)):
    ans += arr2[arr3[i]] * (arr2[arr3[i]] - 1) // 2
print(ans)