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

S = input()
N = len(S)

from collections import defaultdict

reddic = defaultdict(int)
bludic = defaultdict(int)

redarray = [0] * (N+1)
bluarray = [0] * (N+1)

for e,c in enumerate(S):

    if c == "2":
        bludic[e+1] += 2
        bluarray[e+1] += 2
    elif c == "1":
        reddic[e+1] += 1
        bludic[e+1] += 1

        redarray[e+1] += 1
        bluarray[e+1] += 1
    elif c == "0":
        reddic[e+1] += 2
        redarray[e+1] += 2

for i in range(1,N+1):
    redarray[i] += redarray[i-1]
    bluarray[i] += bluarray[i-1]

# print("redarray: ", redarray)
# print("bluarray: ", bluarray)

dp = [ [0] * (2*N+1) for _ in range(2*N+1)]
dp[0][0] = 1
MOD = 998244353

for p in range(1, 2*N+1):
    for r in range(0, p):
        idx = p if p <= N else N
        if r < redarray[idx]:
            dp[p][r+1] += dp[p-1][r] % MOD
        if p-1-r < bluarray[idx]:
            dp[p][r] += dp[p-1][r] % MOD
    # print("{:3d}".format(p), dp[p])

print(dp[2*N][redarray[N]]%MOD)

### FIXED CODE ###

# from : https://twitter.com/tempura_cpp/status/1094238517784326144

S = input()
N = len(S)
MOD = 998244353

red = []
blue = []

for i in range(N):
    if S[i] == "0": # two red balls 
        red.append(i)
        red.append(i)
    if S[i] == "1": # red, blue
        red.append(i)
        blue.append(i)
    if S[i] == "2": # two blue 
        blue.append(i)
        blue.append(i)

DP = [ [0]*4020 for _ in range(4020)] # DP[rsize][bsize] : # of patterns for 
                                           # the case red size is i, blue size is j. 
                                                        
DP[0][0] = 1                          # S = "" pattern.

rsize = len(red)
bsize = len(blue)
# print("red: {}, blue: {}".format(red, blue))

# S = 12001021211100201020
# red:  [0, 2, 2, 3, 3, 4, 5, 5, 7, 9, 10, 11, 12, 12, 13, 13, 15, 15, 16, 17, 17, 19, 19], 
# blue: [0, 1, 1, 4, 6, 6, 7, 8, 8, 9, 10, 11, 14, 14, 16, 18, 18]

# sample
# b r r r r r b
# b r r r r r b
# blue : [0,0, 6,6]
# red  : [1,1,2,2,3,3,4,4,5,5]
# it is hard to use blue[2] = 6, you have to use red 1-5
# this constraint is represented with m = i+j


for i in range(rsize+1):
    for j in range(bsize+1):

        DP[i][j] %= MOD

        m = i+j

        if j < bsize and blue[j] <= m:
            DP[i][j+1] += DP[i][j]

        if i < rsize and red[i] <= m:
            DP[i+1][j] += DP[i][j]


print(DP[rsize][bsize] % MOD)
### BUGGY CODE ###

while True:
	n=int(input())
	if n==0:
		break
	A=[]
	for i in range(n):
		A.append(int(input()))
	MAX=[0]*(len(A))
	end=len(A)
	for i in range(end):
		for j in range(i+1,end+1):
			if MAX[i]<sum(A[i:j]):
				MAX[i]=sum(A[i:j])
	MAX.sort()
	print(MAX[-1])

### FIXED CODE ###

while True:
	n=int(input())
	if n==0:
		break
	A=[]
	for i in range(n):
		x=int(input())
		A.append(x)

	B=[int()]*n
	B[0]=A[0]
	for i in range(1,n):
		if A[i]>=A[i]+B[i-1]:
			B[i]=A[i]
		else:
			B[i]=A[i]+B[i-1]
	print(max(B))
### BUGGY CODE ###

from math import factorial
mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def nCr(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

def nPr(n,r):
    if not (0 <= r <= n):
        return 0
    return nCr(n, r) * g1[r] % mod


N,M=map(int,input().split())
ans=nPr(M,N)**2%mod
for i in range(1,N+1):
    p=nPr(M-i,N-i)**2%mod
    p=p*nPr(N,i)%mod
    p=p*nCr(M,i)%mod
    ans-=((-1) ** ((i % 2) ^ 1))*p
    ans%=mod
print(ans%mod)

### FIXED CODE ###

from math import factorial
mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def nCr(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

def nPr(n,r):
    if not (0 <= r <= n):
        return 0
    return nCr(n, r) * g1[r] % mod


N,M=map(int,input().split())
ans=nPr(M,N)**2%mod
for i in range(1,N+1):
    p=nPr(M-i,N-i)**2%mod
    p=p*nPr(N,i)%mod
    p=p*nCr(M,i)%mod
    ans-=((-1) ** ((i % 2) ^ 1))*p
    ans%=mod
print(ans%mod)
### BUGGY CODE ###

import itertools
n = input()
l = list(map(int,input().split()))
ans = 0
for i in list(itertools.combinations(l,3)):
    i = sorted(i)
    a,b,c = i[0],i[1],i[2]
    if c<a+b:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
l = sorted(l)
ans = 0
for c in range(n):
    a=0
    b=c-1
    while a<b:
        if l[a]+l[b]>l[c]:
            ans+=b-a
            b-=1
        else:
            a+=1
print(ans)
### BUGGY CODE ###


import bisect
import collections
import itertools


def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint2d(rows): return [getints() for _ in range(rows)]
def getgrid(rows): return [input() for _ in range(rows)]
def array1d(n, value): return [value for _ in range(n)]
def array2d(n, m, value): return [array1d(m, value) for _ in range(n)]

n,a,b=getints()
hs=[getint() for _ in range(n)]

min_cast = 0
max_cast = 10 ** 10
c = a-b

while min_cast < max_cast:
    cast = (min_cast + max_cast) // 2
    values= list(filter(lambda s: s > 0, map(lambda s: s - b*cast, hs)))
    need = sum(map(lambda v: (v + c - 1) // c, values))
    if need <= cast:
        max_cast = cast
    else:
        min_cast = cast + 1

print(min_cast)

### FIXED CODE ###


import bisect
import collections
import itertools


def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint2d(rows): return [getints() for _ in range(rows)]
def getgrid(rows): return [input() for _ in range(rows)]
def array1d(n, value): return [value for _ in range(n)]
def array2d(n, m, value): return [array1d(m, value) for _ in range(n)]

n,a,b=getints()
hs=[getint() for _ in range(n)]
mx=max(hs)

min_cast = 0
max_cast = mx+1
c = a-b

hs = list(sorted(hs,reverse=True))

while min_cast < max_cast:
    cast = (min_cast + max_cast) // 2
    #values= list(filter(lambda s: s > 0, map(lambda s: s - b*cast, hs)))
    #need = sum(map(lambda v: (v + c - 1) // c, values))
    need = 0
    dec = b * cast
    for v in hs:
        v = v - dec
        if v <= 0:
            break
        need += (v + c - 1) // c
    if need <= cast:
        max_cast = cast
    else:
        min_cast = cast + 1

print(min_cast)
### BUGGY CODE ###

import math
Q_SIZE = math.pow(10,5) 
Q = int(input())

Count_Prime = [False for i in range(int(Q_SIZE//2))] 
C_Range_L = 0 
C_Range_R = 0

def check_range(L,R):
    for i in range(L,R+1,2): 
        if(isprime(i) and isprime((i+1)/2)): 
            Count_Prime[i//2] = 1


def isprime(n): 
    if n < 2 : return False 
    if n == 2 : return True 
    if n % 2 == 0 : return False

    for i in range(3,int(math.sqrt(n))+1,2):
        if n % i == 0:
            return False
    return True

for i in range(Q): 
    l,r = map(int, input().split())

    if(C_Range_L == 0 and C_Range_R == 0):
        check_range(l,r+1)
        C_Range_L = l
        C_Range_R = r

    if(C_Range_L > l):
        check_range(l,C_Range_L+1)
        C_Range_L = l

    if(r > C_Range_R):
        check_range(C_Range_R,r+1)
        C_Range_R = r

    print(sum(Count_Prime[l//2:r//2+1]))

### FIXED CODE ###

import math
Q_SIZE = int(math.pow(10,5))
Q = int(input())

Check_Prime = [True for i in range(Q_SIZE+1)]
Count_like = [0 for i in range(Q_SIZE//2)]

Check_Prime[0] = False
Check_Prime[1] = False

for i in range(2,Q_SIZE+1):
    if(Check_Prime[i] == True):
        for j in range(i+i,Q_SIZE+1,i):
            Check_Prime[j] = False
            
for i in range(1,Q_SIZE//2):
    if(Check_Prime[i*2+1] == True and Check_Prime[int(((i*2+1)+1)/2)] == True):
        Count_like[i] = Count_like[i-1] + 1
    else:
        Count_like[i] = Count_like[i-1]

for i in range(Q):
    l,r = map(int,input().split())
    if( l == 1):
        print(Count_like[r//2] - Count_like[l//2])
    else:
        print(Count_like[r//2] - Count_like[l//2 - 1])
### BUGGY CODE ###

from collections import deque
N = int(input())
A = deque(map(int, input().split()))
mod = 10**9 + 7
M = len(bin(max(A))) - 2
ans = 0
bitlist = [1]
for k in range(M):
    bitlist.append(bitlist[-1]*2%mod)
counter = [0 for _ in range(M)]

for k in range(N):
    a = A.pop()
    c = 0
    while c < M:
        b = a & 1
        if b == 0:
            ans += counter[-c-1]*bitlist[c]%mod
            ans %= mod
        else:
            ans += (k-counter[-c-1])*bitlist[c]%mod
            ans %= mod
            counter[-c-1] += 1
        c += 1
        a >>= 1
print(ans)




### FIXED CODE ###

from collections import deque
N = int(input())
A = deque(map(int, input().split()))
mod = 10**9 + 7
M = len(bin(max(A))) - 2
ans = 0
bitlist = [1]
for k in range(M):
    bitlist.append(bitlist[-1]*2%mod)
counter = [0 for _ in range(M)]

for k in range(N):
    a = A.pop()
    c = 0
    while c < M:
        b = a & 1
        if b == 0:
            ans += counter[-c-1]*bitlist[c]%mod
            ans %= mod
        else:
            ans += (k-counter[-c-1])*bitlist[c]%mod
            ans %= mod
            counter[-c-1] += 1
        c += 1
        a >>= 1
print(ans)
### BUGGY CODE ###

n = int(input())
cs = sorted((tuple(map(int, input().split())) for _ in range(n)), key=sum)
dp = [0]
for m, (h, p) in enumerate(cs):
    if dp[-1] <= h:
        dp.append(dp[-1] + p)
        bak = 3
    else:
        bak = 2
    for i in range(len(dp) - bak, -1, -1):
        if dp[i] <= h:
            dp[i + 1] = min(dp[i + 1], dp[i] + p)

print(len(dp) - 1)


### FIXED CODE ###

n = int(input())
cs = sorted((tuple(map(int, input().split())) for _ in range(n)), key=sum)
dp = [0]
for m, (h, p) in enumerate(cs):
    if dp[-1] <= h:
        dp.append(dp[-1] + p)
        bak = 3
    else:
        bak = 2
    for i in range(len(dp) - bak, -1, -1):
        if dp[i] <= h:
            dp[i + 1] = min(dp[i + 1], dp[i] + p)

print(len(dp) - 1)
### BUGGY CODE ###

from collections import defaultdict

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

D = defaultdict(int)
E = defaultdict(int)

for x in A:
  Flag = True

  if E[x] >= 1:
    D[x] += 1
    continue

  for j in D.keys():
    if x%j == 0:
      Flag = False
      break
    
  if Flag:
    D[x] += 1
    E[x] += 1

ans = len([i for i in D if D[i] == 1])

print(ans)

### FIXED CODE ###


import math
from collections import defaultdict

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

D = defaultdict(int)

AM = A[-1]
dp = [True]*(AM)

for x in A:
  if dp[x-1]:
    temp = 2 * x
    while temp <= AM:
      dp[temp-1] = False
      temp += x

for x in A:
  if dp[x-1]:
    D[x] += 1

ans = len([i for i in D if D[i] == 1])

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

n = int(input())
a = list(map(int,input().split()))
a.sort()
ans = 0
def count(i):
    res = 0
    for x in a[i:]:
        if x - a[i] <= 1:
            res += 1
    for y in a[:i]:
        if a[i] - y <= 1:
            res += 1
    return res

for i in range(n):
    ans = max(ans,count(i))
print(ans)

### FIXED CODE ###

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

s = [0]*(a[-1]+1)
for i in range(n):
    s[a[i]] += 1
ans = 0
if a[-1] - 1 > 0:
    for i in range(1,a[-1]):
        ans = max(ans, s[i] + s[i-1] + s[i+1])
    print(ans)
else:
    print(max(s))
### BUGGY CODE ###

def main():
    import bisect
    import sys
    input = sys.stdin.readline
    n,m,q=map(int,input().split())
    train=[[] for i in range(n)]
    for i in range(m):
        l,r=map(int,input().split())
        train[l-1].append(r-1)
    for i in range(n):
        train[i].sort()
    for i in range(q):
        p,q_=map(int,input().split())
        ans=0
        for i in range(p-1,q_):
            ans+=bisect.bisect_right(train[i],q_-1)
        print(ans)

if __name__ == '__main__':
    main()



### FIXED CODE ###

n,m,q=map(int,input().split())
train=[[0]*n for i in range(n)]
for i in range(m):
    l,r=map(int,input().split())
    train[l-1][r-1]+=1
for i in range(n):
    for j in range(n-1):
        train[i][j+1]+=train[i][j]
for i in range(q):
    p,q_=map(int,input().split())
    ans=0
    for j in range(p-1,q_):
        ans+=train[j][q_-1]
    print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [None] * N

for i in range(N):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = abs(h[0]-h[1])
    else:
        ans = 10**10
        for j in range(1, K+1):
            if j > i:
                break
            ans = min(ans, dp[i-j] + abs(h[i-j]-h[i]))
        dp[i] = ans

print(dp[N-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * n

for i in range(n):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = abs(h[0]-h[1])
    else:
        costs = []
        for j in range(1, k+1):
            if j > i:
                break
            if abs(h[i-j]-h[i]) == 0:
                costs.append(dp[i-j])
                break
            costs.append(dp[i-j] + abs(h[i-j]-h[i]))

        # if i == 3:
        #     print(costs)
        dp[i] = min(costs)

#print(dp)
print(dp[n-1])
### BUGGY CODE ###

def main():
    n = int(input())
    l = []
    for x in range(1,101):
        for y in range(1, 101):
            for z in range(1, 101):
                l.append(x**2+y**2+z**2+x*y+y*z+z*x)

    for i in range(1,n+1):
        print(sum(i == j for j in l))
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    dp=[0]*(10000+1)
    for x in range(1,101):
        for y in range(1, 101):
            for z in range(1, 101):
                num = x**2+y**2+z**2+x*y+y*z+z*x
                if num <= 10000:
                    dp[num] += 1
    [print(dp[i]) for i in range(1,n+1)]

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

import sys
# input処理を高速化する
input = sys.stdin.readline

N,X,Y = map(int,input().split())

# dp =[[0]*(N) for _ in range(N)]
# for j in range(N-1):
#     dp[j][j+1]=1
#     dp[j+1][j]=1

# # 線がついているところ
# dp[X-1][Y-1] = 1
# dp[Y-1][X-1] = 1

# print(*dp,sep="\n")

def dist(s,g):
    if s<=X and Y<=g:
        return X-s + 1 + g-Y
    elif s==X and g==Y:
        return 1
    else:
        return min(g-s,abs(s-X)+1+abs(g-Y),abs(s-Y)+1+abs(g-X))

for k in range(1,N):
    cnt =0

    if k==1:
        print(N)
    else:
        for i in range(1,N+1):
            for j in range(i+1,N+1):
                if dist(i,j) == k:
                    cnt+=1
        print(cnt)
    
         



### FIXED CODE ###

n,x,y = map(int,input().split())

x,y = x-1,y-1

d={}
for k in range(1,n):
    d[k]=0


for i in range(n):
    for j in range(i+1,n):
     
        dist=min(abs(i-j) , abs( i - x ) + 1 + abs(y - j) ,abs( i - y ) + 1 + abs(x - j))

        d[dist]+=1

for k in range(1,n):
    print(d[k])
### BUGGY CODE ###

from collections import Counter
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

n, x, y = map(int, input().split())
d = [[float("inf")]*n for i in range(n)] 

for i in range(n-1):
    d[i][i+1] = 1
    d[i+1][i] = 1
d[x-1][y-1] = 1
d[y-1][x-1] = 1
for i in range(n):
    d[i][i] = 0
warshall_floyd(d)

L = [0] * (n**2)
for i in range(n):
    for j in range(n):
        L[n*i+j] = d[i][j]
D = Counter(L)
for i in range(1, n):
    print(D[i]//2)

### FIXED CODE ###

import collections
n, x, y = map(int, input().split())
d = [[0]*(i+1) for i in range(n)]
x -= 1
y -= 1
for i in range(n):
    for j in range(i+1):
        d[i][j] = min(i-j, abs(x-j)+abs(y-i)+1)
L = []
for i in range(n):
    for dd in d[i]:
        L.append(dd)
C = collections.Counter(L)
for i in range(1, n):
    print(C[i])
### BUGGY CODE ###

cij =[]
for i in range(3):
    cij.append(list(map(int, input().split(" "))))

bi_list = []
for b1 in range(-500000, 500000):
    b2 = b1 - (cij[0][0] - cij[0][1])
    b3 = b1 - (cij[0][0] - cij[0][2])

    a1 = cij[0][0]+cij[0][1]+cij[0][2] -b1-b2-b3
    a2 = cij[1][0]+cij[1][1]+cij[1][2] -b1-b2-b3
    a3 = cij[2][0]+cij[2][1]+cij[2][2] -b1-b2-b3
    if a1/3+b1 ==cij[0][0] and a1/3+b2 ==cij[0][1] and a1/3+b3 ==cij[0][2] and a2/3+b1 ==cij[1][0] and a2/3+b2 ==cij[1][1] and a2/3+b3 ==cij[1][2] and a3/3+b1 ==cij[2][0] and a3/3+b2 ==cij[2][1] and a3/3+b3 ==cij[2][2]:
            print("Yes")
            exit()

print("No")

### FIXED CODE ###

cij =[]
for i in range(3):
    cij.append(list(map(int, input().split(" "))))

bi_list = []
for b1 in range(-50000, 50000):
    b2 = b1 - (cij[0][0] - cij[0][1])
    b3 = b1 - (cij[0][0] - cij[0][2])

    a1 = cij[0][0]+cij[0][1]+cij[0][2] -b1-b2-b3
    a2 = cij[1][0]+cij[1][1]+cij[1][2] -b1-b2-b3
    a3 = cij[2][0]+cij[2][1]+cij[2][2] -b1-b2-b3
    if a1/3+b1 ==cij[0][0] and a1/3+b2 ==cij[0][1] and a1/3+b3 ==cij[0][2] and a2/3+b1 ==cij[1][0] and a2/3+b2 ==cij[1][1] and a2/3+b3 ==cij[1][2] and a3/3+b1 ==cij[2][0] and a3/3+b2 ==cij[2][1] and a3/3+b3 ==cij[2][2]:
            print("Yes")
            exit()

print("No")
### BUGGY CODE ###

import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
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 [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[inf]*w for _ in range(h)]

  sharp_cnt=0
  for x in field:
    sharp_cnt+=x.count('#')

  q.append((0,0,0))

  while len(q)>0:
    y,x,cnt=q.pop()
    counter[y][x]=cnt

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='#':
          if counter[ny][nx]>3000 and counter[ny][nx]<4000:
            continue
          if counter[ny][nx]>cnt:
            q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]+1

  if step_cnt==inf+1:
    return -1

  return h*w-sharp_cnt-step_cnt

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
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 [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[inf]*w for _ in range(h)]

  sharp_cnt=0
  for x in field:
    sharp_cnt+=x.count('#')

  q.append((0,0,1))

  while len(q)>0:
    y,x,cnt=q.pop()
    if counter[y][x]<cnt:
      continue
    counter[y][x]=cnt

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='#':

          if counter[ny][nx]>cnt+1:
            q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]

  if step_cnt==inf:
    return -1

  return h*w-sharp_cnt-step_cnt

# main()
print(main())
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

nCr = {}
def cmb(n, r):
    if n == 1: return 0
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


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

L=[0]
s=0
for i in range(N):
    s+=a[i]
    L.append(s)

L=sorted(L)

s=0
t=L[0]
c=1
for i in range(1,len(L)):
    if(t==L[i]):
        c+=1
    else:
        s+=cmb(c,2)
        t=L[i]
        c=1
else:
    s+=cmb(c,2)
print(s)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)

nCr = {}
def cmb(n, r):
    if n == 1: return 0
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


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

L=[0]
s=0
for i in range(N):
    s+=a[i]
    L.append(s)

L=sorted(L)

s=0
t=L[0]
c=1
for i in range(1,len(L)):
    if(t==L[i]):
        c+=1
    else:
        s+=cmb(c,2)
        t=L[i]
        c=1
else:
    s+=cmb(c,2)
print(s)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

s = input().strip()

import functools

@functools.lru_cache(maxsize=None)
def dfs(start, remain):
    if len(remain) == 0:
        return 1
    else:
        ans = 0
        for i in range(1, 3):
            if start == remain[:i]:
                continue
            else:
                ans = max(ans, 1 + dfs(remain[:i], remain[i:]))
        return ans

@functools.lru_cache(maxsize=None)
def _dfs(s):
    if len(s) <= 1:
        return len(s)
    if len(s) == 2:
        if s[0] == s[1]:
            return 1
        else:
            return 2
    if len(s) >= 3:
        if s[0] == s[1]:
            return max(1 + _dfs(s[2:]), 2 + _dfs(s[3:]))
        else:
            return max(1 + _dfs(s[1:]), 1 + _dfs(s[2:]))

ans = 0
if len(s) == 1:
    print(ans)
    sys.exit(0)
print(_dfs(s))


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

s = input().strip()
if len(s) == 1:
    print(0)
    sys.exit(0)
if len(s) == 2 and s[0] == s[1]:
    print(0)
    sys.exit(0)

# [i][0]: index iが1文字分割
# [i][1]: index iが2文字分割
dp = [[0] * 2 for _ in range(len(s))]
# 3文字以上では1文字/2文字の仮想結果が使われる
# 1文字
dp[0][0] = dp[0][1] = 1
# 2文字
if s[0] == s[1]:
    # 実際には常に2文字分割になる
    dp[1][0] = dp[1][1] = 1
else:
    dp[1][0] = 2
    dp[1][1] = 1

# 3文字以上
for i in range(2, len(s)):

    # [i][0]: 末尾の分割を1文字にする場合

    # 末尾2文字が同じ場合
    # - 1つ前を2文字分割にしなくてはならない
    if s[i] == s[i-1]:
        dp[i][0] = dp[i-1][1] + 1
    # 末尾2文字が異なる場合
    # - 1つ前が1文字分割
    # - 1つ前が2文字分割
    else:
        dp[i][0] = max(dp[i-1][0] + 1, dp[i-1][1] + 1)


    # [i][1]: 末尾の分割を2文字にする場合
    # 末尾前の2文字が末尾の2文字と同じ場合
    # 末尾前を1文字分割にしなくてはならない
    if s[i-3:i-1] == s[i-1:i+1]:
        dp[i][1] = dp[i-2][0] + 1
    # 末尾前の2文字が末尾の2文字と異なる場合
    # - 末尾前が1文字分割
    # - 末尾前が2文字分割
    else:
        dp[i][1] = max(dp[i-2][0] + 1, dp[i-2][1] + 1)

print(max(dp[-1][0], dp[-1][1]))
### BUGGY CODE ###

import math

# doubling

n, k = list(map(int, input().split()))
nums = [-1] + list(map(int, input().split()))
doubling =[[0 for _ in range(n + 1)] for _ in range(int(math.log2(k)) + 1)]

for i in range(len(doubling)):
	for j in range(1, n + 1):
		if i == 0:
			doubling[i][j] = nums[j]
		else:
			doubling[i][j] = doubling[i - 1][doubling[i - 1][j]]

cur = 1
for i, x in enumerate(bin(k)[2:][::-1]):
	if x == "1":
		cur = doubling[i][cur]
print(cur)


### FIXED CODE ###

import sys
n, k = list(map(int, input().split()))
nums = [-1] + list(map(int, input().split()))

visited = [0 for _ in range(n + 1)]
path = [1]
cur = 1
visited[1] = 1
for i in range(k):
	cur = nums[cur]
	path.append(cur)
	if visited[cur] == 1:
		for idx, val in enumerate(path):
			if val == cur:
				break
		# print(k, idx, path)
		# print((k - idx) % (len(path) - idx - 1))
		print(path[idx + (k - idx) % ((len(path) - idx - 1))])
		sys.exit()
	else:
		visited[cur] = 1
print(cur)
### BUGGY CODE ###

[N, K] = list(map(int, input().split()))
A = list(map(int, input().split()))
P = 1

for i in range(K):
    P = P*A[i]

st = 0
la = K

for i in range(N-K):
    P2 = (P/A[st])*A[la]
    if P2 > P:
        print('Yes')
    else:
        print('No')
    st += 1
    la += 1
    P = P2

### FIXED CODE ###

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

st = 0
la = K

for i in range(N-K):
    if A[la] > A[st]:
        print('Yes')
    else:
        print('No')
    st += 1
    la += 1