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

## xiのpopcount（1の数）はxのpopcount+1または-1
n=int(input())
x=input()
f={0:0,1:1,2:1,3:2}
for i in range(2,n):
    f[2**i]=1
# print(f)
for i in range(len(x)):
    if x[i]=='1':
        x_changed=x[:i]+'0'+x[i+1:]
    else:
        x_changed=x[:i]+'1'+x[i+1:]
    num_changed=int(x_changed,2)
    add=[]
    tmp=num_changed
    while tmp not in f:
        popcount=format(tmp,'b').count('1')
        add.append(tmp)
        tmp%=popcount
    while len(add)>0:
        cnt=f[tmp]
        tmp=add.pop()
        f[tmp]=cnt+1
    print(f[num_changed])

### FIXED CODE ###

## 最初のmodをどうにか高速にやりたい → modの性質を使う
## xiのpopcount（1の数）はxのpopcount+1または-1
n=int(input())
x_str=input()
x_popcount=x_str.count('1')
dp=[0]*(x_popcount+1)
for i in range(1,x_popcount+1):
    popcount=format(i,'b').count('1')
    dp[i]=dp[i%popcount]+1
# print(dp)
# x=int(x_str,2)
if x_popcount>1:
    pows_minus=[pow(2,i,(x_popcount-1)) for i in range(n)]
    # x_minus=x%(x_popcount-1)
    x_minus=0
    for i in range(n):
        if x_str[i]=='1':
            x_minus+=pows_minus[n-1-i]
pows_plus=[pow(2,i,(x_popcount+1)) for i in range(n)]
# x_plus=x%(x_popcount+1)
x_plus=0
for i in range(n):
    if x_str[i]=='1':
        x_plus+=pows_plus[n-1-i]

for i in range(len(x_str)):
    ## xi=xi mod popcount(x)+-1
    xi=-1
    if x_str[i]=='1':
        if x_popcount>1: ## else: xi=-1
            xi=(x_minus-pows_minus[n-1-i])%(x_popcount-1)
    else:
        xi=(x_plus+pows_plus[n-1-i])%(x_popcount+1)
    if xi==-1:
        print(0)
    else:
        print(dp[xi]+1)
### BUGGY CODE ###

import bisect
h,w=map(int,input().split())
g = [['#']*(w+2) for i in range(h+2)]
for i in range(h):
  g[i+1][1:-1] = list(input())
L=[[0]*(w+2) for i in range(h+2)]
R=[[0]*(w+2) for i in range(h+2)]
D=[[0]*(w+2) for i in range(h+2)]
U=[[0]*(w+2) for i in range(h+2)]
for i in range(h+2):
  for j in range(w+2):
    if g[i][j]=="#":
      L[i][j]=0
    else:
      L[i][j]=L[i][j-1]+1
for i in range(h+2):
  for j in range(w+1,-1,-1):
    if g[i][j]=="#":
      R[i][j]=0
    else:
      R[i][j]=R[i][j+1]+1
for i in range(h+2):
  for j in range(w+2):
    if g[i][j]=="#":
      D[i][j]=0
    else:
      D[i][j]=D[i-1][j]+1
for i in range(h+1,-1,-1):
  for j in range(w+2):
    if g[i][j]=="#":
      U[i][j]=0
    else:
      U[i][j]=U[i+1][j]+1
Max=0
for i in range(h+2):
  for j in range(w+2):
    a=0
    a=L[i][j]+R[i][j]+D[i][j]+U[i][j]
    if a>Max:
      Max=a
print(Max-3)

### FIXED CODE ###

import bisect
h,w=map(int,input().split())
g = [['#']*(w+2) for i in range(h+2)]
for i in range(h):
  g[i+1][1:-1] = list(input())
L=[[0]*(w+2) for i in range(h+2)]
R=[[0]*(w+2) for i in range(h+2)]
D=[[0]*(w+2) for i in range(h+2)]
U=[[0]*(w+2) for i in range(h+2)]
for i in range(h+2):
  for j in range(w+2):
    if g[i][j]=="#":
      L[i][j]=0
    else:
      L[i][j]=L[i][j-1]+1
for i in range(h+2):
  for j in range(w+1,-1,-1):
    if g[i][j]=="#":
      R[i][j]=0
    else:
      R[i][j]=R[i][j+1]+1
for i in range(h+2):
  for j in range(w+2):
    if g[i][j]=="#":
      D[i][j]=0
    else:
      D[i][j]=D[i-1][j]+1
for i in range(h+1,-1,-1):
  for j in range(w+2):
    if g[i][j]=="#":
      U[i][j]=0
    else:
      U[i][j]=U[i+1][j]+1
Max=0
for i in range(h+2):
  for j in range(w+2):
    a=0
    a=L[i][j]+R[i][j]+D[i][j]+U[i][j]
    if a>Max:
      Max=a
print(Max-3)
### BUGGY CODE ###

n = int(input())
s = input()

s1 = s[:n]
s2 = s[n:]

d1 = dict()
for i in range(1 << n):
    rd = ''
    bl = ''
    for j in range(n):
        if (i >> j) & 1:
            rd = rd + s1[j]
        else:
            bl = s1[j] + bl
    tpl = (rd, bl)
    d1[tpl] = d1.get(tpl, 0) + 1

d2 = dict()
for i in range(1 << n):
    rd = ''
    bl = ''
    for j in range(n):
        if (i >> j) & 1:
            rd = rd + s2[j]
        else:
            bl = s2[j] + bl
    tpl = (bl, rd)
    d2[tpl] = d2.get(tpl, 0) + 1

ans = 0
for k1, v1 in d1.items():
    ans += v1 * d2.get(k1, 0)
print(ans)

### FIXED CODE ###

def main():
    from collections import defaultdict

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

    L, R = S[:N], S[N * 2 - 1:N - 1:-1]

    def make_counter(s: str) -> defaultdict(int):
        ret = defaultdict(int)
        for bit in range(1 << N):
            red, blue = '', ''
            for j in range(N):
                if (bit >> j) & 1:
                    red += s[j]
                else:
                    blue += s[j]

            ret[red + '_' + blue] += 1
        return ret

    ld = make_counter(L)
    rd = make_counter(R)

    print(sum(ld[key] * rd[key] for key in ld))


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

from itertools import accumulate

n, m, k = map(int, input().split())
(*a,) = accumulate(map(int, input().split()))
(*b,) = accumulate(map(int, input().split()))
a = (0,) + tuple(i for i in a if i <= k)
b = (0,) + tuple(i for i in b if i <= k)
ans = set()
for i in range(len(a)):
    tmp = k - a[i]
    for j in range(len(b) - 1, -1, -1):
        if b[j] <= tmp:
            ans.add(i + j)
            break
print(max(ans))


### FIXED CODE ###

from itertools import accumulate
from bisect import bisect

n, m, k = map(int, input().split())
(*a,) = accumulate(map(int, input().split()))
(*b,) = accumulate(map(int, input().split()))
a = (0,) + tuple(i for i in a if i <= k)
b = tuple(i for i in b if i <= k)
print(max(i + bisect(b, k - a[i]) for i in range(len(a))))
### BUGGY CODE ###

from collections import deque
import sys


H, W = [int(_) for _ in input().split()]

queues = []


def f(x, i):
    for j in range(W):
        if x[j] == '#':
            queues.append(deque([[j, i, 0]]))
    return list(x)


M = [f(input(), i) for i in range(H)]


depth_now = 0
depth = 0
while True:
    for q in queues:
        while len(q) != 0 and q[0][2] == depth_now:
            p = q.popleft()
            x = p[0]
            y = p[1]
            depth = p[2]
            if x - 1 >= 0 and M[y][x-1] == '.':
                q.append([x-1, y, depth+1])
                M[y][x-1] = '#'
            if x + 1 < W and M[y][x+1] == '.':
                q.append([x+1, y, depth+1])
                M[y][x+1] = '#'
            if y - 1 >= 0 and M[y-1][x] == '.':
                q.append([x, y-1, depth+1])
                M[y-1][x] = '#'
            if y + 1 < H and M[y+1][x] == '.':
                q.append([x, y+1, depth+1])
                M[y+1][x] = '#'
    queues = [q for q in queues if len(q) != 0]
    if len(queues) == 0:
        print(depth_now)
        break
    depth_now += 1


### FIXED CODE ###

from collections import deque
import sys


H, W = [int(_) for _ in input().split()]

M = []
q = deque([])
for i in range(H):
    A = input()
    M.append(list(A))
    for j in range(W):
        if A[j] == '#':
            q.append([j, i, 0])

depth_now = 0
depth = 0
count = 0
while len(q) > 0:
    p = q.popleft()
    x = p[0]
    y = p[1]
    depth = p[2]
    if x - 1 >= 0 and M[y][x-1] == '.':
        q.append([x-1, y, depth+1])
        M[y][x-1] = '#'
    if x + 1 < W and M[y][x+1] == '.':
        q.append([x+1, y, depth+1])
        M[y][x+1] = '#'
    if y - 1 >= 0 and M[y-1][x] == '.':
        q.append([x, y-1, depth+1])
        M[y-1][x] = '#'
    if y + 1 < H and M[y+1][x] == '.':
        q.append([x, y+1, depth+1])
        M[y+1][x] = '#'
print(depth)
### BUGGY CODE ###

def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def ris(): return list(input())
def pli(a): return "".join(list(map(str, a)))

N, M = rli()
keiro = [[False for i in range(N+1)] for j in range(N+1)]
for i in range(M):
    a, b = rli()
    keiro[a][b] = True
    keiro[b][a] = True

flag = False
for i in range(N):
    if(keiro[i][1] and keiro[i][N]):
        flag = True
if(flag):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def ris(): return list(input())
def pli(a): return "".join(list(map(str, a)))

N, M = rli()
keiro = [[False for i in range(2)] for j in range(N+1)]
for i in range(M):
    a, b = rli()
    if(b == 1 or b == N):
        keiro[a][1 if b == 1 else 0] = True
    elif(a == 1 or a == N):
        keiro[b][1 if a == 1 else 0] = True

flag = False
for i in range(2, N):
    if(keiro[i][1] and keiro[i][0]):
        flag = True
if(flag):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

import re

def getinputdata():

    array_result = []    
    data = input()
    array_result.append(data.split(" "))

    flg = True

    try:
        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = True

            else:

                flg = False
    finally:

        return array_result

arr_data = getinputdata()

x=arr_data[0][0]


pattern="ST"


cnt=10**10000
for i in range(cnt):
    
    if x.count("ST")>0:

        x = re.sub(pattern, "", x)
    else:
        
        break
        
print(len(x))


### FIXED CODE ###

from collections import deque
def getinputdata():

    array_result = []    
    data = input()
    array_result.append(data.split(" "))

    flg = True

    try:
        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = True

            else:

                flg = False
    finally:

        return array_result

arr_data = getinputdata()

x=arr_data[0][0]

b = deque([])

for v in x:
    
    if v=="S":
        
        b.appendleft(v)
        
    elif v=="T" and (len(b)==0 or b[0]=="T"):
        
        b.appendleft(v)
        
    else:
            
        b.popleft()
            
print(len(b))
### BUGGY CODE ###

from math import floor
n, p = map(int, input().split())
if n == 1:
    print(p)
else:
    for i in range(1, floor(p**(1/n))+10):
        if p % i**n ==0:
            res = i
    print(res)


### FIXED CODE ###

n, p = map(int, input().split())
if n == 1:
    print(p)
else:
    for i in range(1, round(p**(1/n))+1):
        if p % i**n ==0:
            res = i
    print(res)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC66 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(n,r):
    if n - r < 0:
        return 0
    return fact[n]*invfact[r]*invfact[n-r] % mod
n = I()
a = LI()
c = list(Counter(a).items())
c.sort(key = itemgetter(1),reverse = True)
x = c[0][0]

fact = [1]*(n+2)
invfact = [1]*(n+2)
for i in range(1,n+2):
    fact[i] = i*fact[i-1]
    invfact[i] = invfact[i-1]*pow(i,mod-2,mod)

lst = []
for i in range(n+1):
    if a[i] == x:
        lst.append(i+1)
a,b = lst[0],lst[1]
for i in range(n+1):
    res = 0
    res = (res + comb(n+1,i+1)) % mod
    res = (res - comb((a-1)+(n+1-b),i)) % mod
    print(res)
    

### FIXED CODE ###

#!/usr/bin/env python3
#ABC66 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def f(a, b):
    if b == 0: 
        return 1
    if b % 2 == 0:
        d = f(a, b // 2)
        return d * d % mod
    if b % 2 == 1:
        return (a * f(a, b - 1)) % mod


def comb(n,r):
    if n - r < 0:
        return 0
    return fact[n] * invfact[r] * invfact[n-r] % mod

n = I()
a = LI()
cnt = [0]*(n+1)
for i in range(n+1):
    if cnt[a[i]]:
        a = cnt[a[i]]
        b = i+1
        break
    else:
        cnt[a[i]] = i+1

fact = [1]*(n+2)
invfact = [1]*(n+2)
for i in range(1,n+2):
    fact[i] = i*fact[i-1] % mod
    invfact[i] = invfact[i-1] * f(i,mod-2) % mod

for i in range(n+1):
    res = 0
    res = (res + comb(n+1,i+1)) % mod
    res = (res - comb((a-1)+(n+1-b),i)) % mod
    print(res)
### BUGGY CODE ###

a,b,c,k=map(int,input().split())
cnt=0
for i in range(k):
    if a>0:
        cnt+=1
        a-=1
    else:
        if b>0:
            b-=1
        else:
            if c>0:
                cnt-=1
                c-=1
print(cnt)

### FIXED CODE ###

a,b,c,k=map(int,input().split())
if a>=k:
    print(k)
else:
    if a+b>=k:
        print(a)
    else:
        if a+b+c>=k:
            print(a-(k-(a+b)))
### BUGGY CODE ###

n = int(input())
li = [int(input()) for _ in range(n)]

for a, b in enumerate(li):
  li2 = li[a+1:] + li[:a]
  print(max(li2))

### FIXED CODE ###

n = int(input())
li = [int(input()) for _ in range(n)]

mi = li.index(max(li))
m = max(li)

for a, b in enumerate(li):
  if a != mi:
    print(m)
  else:
    print(max(li[a+1:]+li[:a]))
### BUGGY CODE ###

import sys
import numpy as np
N = int(input())

A = np.zeros(N)
count = 0
for n in range(N):
    A[n] = int(input())

if all(A):
    print(int(sum(A) // 2))
    sys.exit()

B = np.split(A, np.where(A == 0)[0][:])
for item in B:
    count += sum(item) // 2
print(int(count))

### FIXED CODE ###

import sys
N = int(input())

A = [0] * N
count = 0
for n in range(N):
    A[n] = int(input())

if all(A):
    print(sum(A) // 2)
    sys.exit()

index = 0
for n in range(N):
    if A[n] == 0:
        count += (sum(A[index: n]) // 2)
        index = n
count += sum(A[index:]) // 2
print(count)
### BUGGY CODE ###

import math
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
if M % N == 0:
    print(M//N)
else:
    upper = math.ceil(M/N)
    for i in range(upper, 0, -1):
        if M % i == 0:
            break

    print(i)

### FIXED CODE ###

import bisect
import math
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
if M % N == 0:
    print(M//N)
else:
    upper = math.ceil(M/N)
    factor = set()
    for i in range(1, int(M**0.5)+1):
        if M % i == 0:
            factor.add(i)
    
    factor1 = set()
    for i in factor:
        factor1.add(M//i)
    factor |= factor1
    
    factor = sorted(list(factor))
    print(factor[bisect.bisect_right(factor, upper)-1])
### BUGGY CODE ###

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

ans = 1
for i in range(N):
    ans = ans*A[i]

if ans > 10 ** 18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

A = sorted(A)
ans = 1
for i in range(N):
    ans = ans*A[i]
    if ans == 0:
        print(ans)
        exit()
    if ans > 10 ** 18:
        print(-1)
        exit()

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

import itertools
N = int(input())
A = list(map(int, input().split()))
for x in list(itertools.product((0, 1), repeat=N))[::-1]:
    flag = True
    # print(x)
    for i in range(1, N+1):
        tmp = list(x)
        tmp = tmp[i-1::i]
        if sum(tmp) % 2 != A[i-1]:
            flag = False
            break
    if flag:
        total = sum(x)
        if total == 0:
            print(0)
            exit()

        print(total)
        for i, e in enumerate(x):
            if e == 1:
                print(i+1)
        exit()
print("-1")

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
counts = [0] * (N + 1)
ball_counts = 0
balls = []
for i in range(N-1, -1, -1):
    if sum(counts[::i+1][1:]) % 2 != A[i]:
        ball_counts += 1
        balls.append(i+1)
        counts[i+1] = 1
print(ball_counts)
if ball_counts > 0:
    print(*balls)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

password = set()
for i in range(1, N-1):
    for j in range(i+1, N):
        for k in range(j+1, N+1):
            w = S[i-1] + S[j-1] + S[k-1]
            password.add(w)

print(len(password))

### FIXED CODE ###

# -*- coding: utf-8 -*-

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

ans = 0
for i in range(1000):
    pw = list("{0:03d}".format(i))

    if pw[0] in S:
        w1 = S.index(pw[0])
        if pw[1] in S[w1+1:]:
            w2 = w1+1 + S[w1+1:].index(pw[1])
            if pw[2] in S[w2+1:]:
                ans += 1

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
  
n = int(input())
d = make_divisors(n)
d.sort()
a = []
for i in range(len(d)-1):
  if d[i]**2==n:
    a.append([d[i], d[i]])
    break
  for j in range(i+1, len(d)):
    if d[i] * d[j] == n:
      a.append([d[i], d[j]])
      break
m = n
ind = 0
for i in a:
  if abs(i[0]-i[1]) < m:
    m = abs(i[0]-i[1])
    ind = a.index(i)

print(a[ind][0]+a[ind][1]-2)

### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
  
n = int(input())
d = make_divisors(n)
d.sort()
a = []
for i in range(len(d)-1):
  b = n // d[i]
  if b == d[i]:
    a.append([d[i], d[i]])
    break
  for j in range(i+1, len(d)):
    if b == d[j]:
      a.append([d[i], d[j]])
      break
m = n
ind = 0
for i in a:
  if abs(i[0]-i[1]) < m:
    m = abs(i[0]-i[1])
    ind = a.index(i)

print(a[ind][0]+a[ind][1]-2)
### BUGGY CODE ###

from collections import Counter

n = int(input())
xs = [int(c) for c in input().split()]

mod = (10 ** 9) + 7

c = Counter(xs)

for k, v in c.items():
    if v == 2:
        dup = k

dup_idx = [i for i, v in enumerate(xs) if v == dup]

facts = [1]
for i in range(1, n + 3):
    facts.append(facts[-1] * i % mod)

def inv(x):
    return pow(x, mod - 2, mod)

def comb(p, q):
    if (not 0 <= q <= p) or p < 0:
        return 0
    return facts[p] * inv(facts[q]) % mod * inv(facts[p - q]) % mod

tl = n + 1
for l in range(1, n + 2):
    use_no = comb(tl - 2, l)
    use_both = comb(tl - 2, l - 2)
    use_one = comb(tl - 2, l - 1) * 2 - comb(min(dup_idx) + (tl - 1 - max(dup_idx)), l - 1)
    print((use_no + use_both + use_one) % mod)
    # print(use_no,use_both ,use_one)

### FIXED CODE ###

from collections import Counter

n = int(input())
xs = [int(c) for c in input().split()]

mod = (10 ** 9) + 7

c = Counter(xs)

for k, v in c.items():
    if v == 2:
        dup = k

dup_idx = [i for i, v in enumerate(xs) if v == dup]

facts = [1]
for i in range(1, n + 3):
    facts.append(facts[-1] * i % mod)

def inv(x):
    return pow(x, mod - 2, mod)

def comb(p, q):
    if (not 0 <= q <= p) or p < 0:
        return 0
    return facts[p] * inv(facts[q]) % mod * inv(facts[p - q]) % mod

tl = n + 1
for l in range(1, n + 2):
    use_no = comb(tl - 2, l)
    use_both = comb(tl - 2, l - 2)
    use_one = comb(tl - 2, l - 1) * 2 - comb(min(dup_idx) + (tl - 1 - max(dup_idx)), l - 1)
    print((use_no + use_both + use_one) % mod)
    # print(use_no,use_both ,use_one)
### BUGGY CODE ###

import sys

readline = sys.stdin.buffer.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():
  s = list(ns())
  ls = len(s)
  lk = ni()
  if lk * 2 >= ls:
    print(ls)
    return
  dp = [[[0]*ls for _ in range(ls)] for i in range(2)]
  ans = 0
  for i in range(ls):
    dp[0][i][i] = 1
  for k in range(lk+1):
    v = k & 1
    for dis in range(1, ls):
      for i in range(ls - dis):
        j = i + dis
        dp[v][i][j] = 0
        if s[i] == s[j]:
          dp[v][i][j] = dp[v][i+1][j-1] + 2
        elif k:
          dp[v][i][j] = dp[v^1][i+1][j-1] + 2
        dp[v][i][j] = max(dp[v][i][j], dp[v][i+1][j], dp[v][i][j-1])
    ans = max(ans, dp[v][0][-1])

  print(ans)
  return

solve()

### FIXED CODE ###

import sys

readline = sys.stdin.buffer.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():
  s = list(ns())
  ls = len(s)
  lk = ni()
  dp = [[[0]*ls for _ in range(ls)] for i in range(2)]
  ans = 0
  for i in range(ls):
    dp[0][i][i] = 1
  for k in range(lk+1):
    v = k & 1
    for dis in range(1, ls):
      for i in range(ls - dis):
        j = i + dis
        dp[v][i][j] = 0
        if s[i] == s[j]:
          dp[v][i][j] = dp[v][i+1][j-1] + 2
        elif k:
          dp[v][i][j] = dp[v^1][i+1][j-1] + 2
        dp[v][i][j] = max(dp[v][i][j], dp[v][i+1][j], dp[v][i][j-1])
    ans = max(ans, dp[v][0][-1])

  print(ans)
  return

solve()
### BUGGY CODE ###

from collections import deque
import numpy as np
 
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)
S=np.zeros_like(T,dtype=int) 
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
B=T.copy()    
d=0
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue
 
        c=deque()    
        s=0
        c.append(i)
        c.append(j)
        
        t=len(c)//2
        while t>0:
                s+=1
                t=len(c)//2
                for k in range(t):
                        m = c.popleft()
                        n = c.popleft()
                        S[m][n]=s
                        if m != H-1:
                                if T[m+1][n]==0 and S[m+1][n]==0:
                                        c.append(m+1)
                                        c.append(n)
                        if m != 0:
                                if T[m-1][n]==0 and S[m-1][n]==0:
                                        c.append(m-1)
                                        c.append(n)
 
                        if n != W-1:
                                if T[m][n+1]==0 and S[m][n+1]==0:
                                        c.append(m)
                                        c.append(n+1)
                                        
                        if n != 0:
                                if T[m][n-1]==0 and S[m][n-1]==0:
                                        c.append(m)
                                        c.append(n-1)
 
        #print(T)
        d = max(d,s)
        S=np.zeros_like(T,dtype=int)
        
print(d-2)

### FIXED CODE ###

from collections import deque
import numpy as np
 
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)
#T=[]
S=np.zeros_like(T,dtype=int) 
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
#B=T.copy()    
d=0
c=deque()  
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue
 
          
        c.append((i,j))
        S[i][j] = 1
        #c.append(j)
        
        #t=len(c)
        while True:

                try:
                  m,n = c.popleft()
                except IndexError: break
                
                
                for kk in [(m+1,n),(m-1,n),(m,n+1),(m,n-1)]:
                  if not (0<=kk[0]<H and 0<= kk[1] <W): continue
                  if T[kk]==1:continue
                  if S[kk] == 0:
                    c.append(kk)
                    S[kk] = S[m][n]+1        
                        
 
        #print(T)
        d = max(d,np.max(S))
        S=np.zeros_like(T,dtype=int)
        
print(d-1)
### BUGGY CODE ###

N = int(raw_input())
A = map(long, raw_input().split())
ans = 0
for i in range(N):
  for j in range(N+1)[i+1:]:
    if sum(A[i:j]) == 0:
      ans += 1
print ans


### FIXED CODE ###

N = int(raw_input())
A = map(long, raw_input().split())
ans = 0
s = 0L
S = [0L]
for a in A:
  s += a
  S.append(s)
S.sort()
c = S[0]
n = 1
for s in S[1:]:
  if c == s:
    n += 1
  else:
    ans += n*(n-1)/2
    n = 1
    c = s
ans += n*(n-1)/2
#for i in range(N):
#  for j in range(N+1)[i+1:]:
#    if sum(A[i:j]) == 0:
#      ans += 1
print ans