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

import sys
input = sys.stdin.readline

def min_cost_flow(E, s, t, f):
    NN = 2 * N + 6
    G = [[] for _ in range(NN)]
    for a, b, cap, c in E:
        G[a].append([b, cap, c, len(G[b])])
        G[b].append([a, 0, -c, len(G[a])-1])
    prevv = [-1] * NN
    preve = [-1] * NN
    res = 0
    while f > 0:
        dist = [1<<100] * NN
        dist[s] = 0
        update = 1
        while update:
            update = 0
            for v in range(NN):
                if dist[v] == 1<<100: continue
                for i, (b, _cap, c, r) in enumerate(G[v]):
                    if _cap > 0 and dist[b] > dist[v] + c:
                        dist[b] = dist[v] + c
                        prevv[b] = v
                        preve[b] = i
                        update = 1
        if dist[t] == 1<<100:
            return -1
        d = f
        v = t
        while v != s:
            d = min(d, G[prevv[v]][preve[v]][1])
            v = prevv[v]
        f -= d
        res += d * dist[t]
        v = t
        while v != s:
            G[prevv[v]][preve[v]][1] -= d
            G[v][G[prevv[v]][preve[v]][3]][1] += d
            v = prevv[v]
    return res

E = []
N = int(input())
su = 0
INF = 1 << 31
for i in range(N):
    x, y, cnt = map(int, input().split())
    E.append((2*N+4, i, cnt, 0))
    E.append((i, 2*N, cnt, x + y + INF))
    E.append((i, 2*N+1, cnt, x - y + INF))
    E.append((i, 2*N+2, cnt, - x + y + INF))
    E.append((i, 2*N+3, cnt, - x - y + INF))
    su += cnt

for i in range(N):
    x, y, cnt = map(int, input().split())
    E.append((i+N, 2*N+5, cnt, 0))
    E.append((2*N, i+N, cnt, - x - y + INF))
    E.append((2*N+1, i+N, cnt, - x + y + INF))
    E.append((2*N+2, i+N, cnt, x - y + INF))
    E.append((2*N+3, i+N, cnt, x + y + INF))

print(su * INF * 2 - min_cost_flow(E, 2*N+4, 2*N+5, su))


### FIXED CODE ###

from networkx import*
N = int(input())
G = MultiDiGraph()
for i in range(N):
    x, y, c = map(int, input().split())
    G.add_node(i, demand = -c)
    G.add_weighted_edges_from([(i, -1, x + y)], capacity = c)
    G.add_weighted_edges_from([(i, -2, x - y)], capacity = c)
    G.add_weighted_edges_from([(i, -3, -x + y)], capacity = c)
    G.add_weighted_edges_from([(i, -4, -x - y)], capacity = c)
for i in range(N):
    x, y, c = map(int, input().split())
    G.add_node(N + i, demand = c)
    G.add_weighted_edges_from([(-1, N + i, -x - y)], capacity = c)
    G.add_weighted_edges_from([(-2, N + i, -x + y)], capacity = c)
    G.add_weighted_edges_from([(-3, N + i, x - y)], capacity = c)
    G.add_weighted_edges_from([(-4, N + i, x + y)], capacity = c)

print(-min_cost_flow_cost(G))
### BUGGY CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,k = map(int,ipt().split())
    a = list(map(int,ipt().split()))
#    n = 2*10**5
#    k = 2*10**5
#    a = [i+1 for i in range(n)]
    nxt = [-1]*(n)
    pa = [-1]*(2*10**5+1)
    for i,ai in enumerate(a*2):
        pai = pa[ai]
        if pai == -2:
            continue
        if pai == -1:
            pa[ai] = i
        else:
            nxt[pai] = i-pai+1
            if i <= n-1:
                pa[ai] = i
            else:
                pa[ai] = -2
    dbl = [nxt]
    ni = 1
    while ni <= n*k:
        nnxt = [0]*n
        pnxt = dbl[-1]
        for i in range(n):
            nnxt[i] = pnxt[i]+pnxt[(i+pnxt[i])%n]
        dbl.append(nnxt)
        if min(nnxt) > n*k:
            break
        ni *= 2
    np = 0
    ld = len(dbl)
    ni = len(dbl)-1
#    print(dbl)
    while ni >= 0:
        db = dbl[ni]
        if db[np%n] < n*k-1-np:
            np += db[np%n]
        else:
            ni -= 1
#        print(np)
    ans = []
    for i in range(np%n,n):
        ai = a[i]
        if ai in ans:
            ans = ans[:ans.index(ai)]
        else:
            ans.append(ai)
    print(" ".join(map(str,ans)))



    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,k = map(int,ipt().split())
    a = list(map(int,ipt().split()))
#    n = 2*10**5
#    k = 2*10**5
#    a = [i+1 for i in range(n)]
    nxt = [-1]*(n)
    pa = [-1]*(2*10**5+1)
    for i,ai in enumerate(a*2):
        pai = pa[ai]
        if pai == -2:
            continue
        if pai == -1:
            pa[ai] = i
        else:
            nxt[pai] = i-pai+1
            if i <= n-1:
                pa[ai] = i
            else:
                pa[ai] = -2
    dbl = [nxt]
    ni = 1
    while ni <= n*k:
        nnxt = [0]*n
        pnxt = dbl[-1]
        for i in range(n):
            nnxt[i] = pnxt[i]+pnxt[(i+pnxt[i])%n]
        dbl.append(nnxt)
        if min(nnxt) > n*k:
            break
        ni *= 2
    np = 0
    ld = len(dbl)
    ni = len(dbl)-1
#    print(dbl)
    for db in dbl[::-1]:
        while True:
            if db[np%n] < n*k-1-np:
                np += db[np%n]
            else:
                break
#        print(np)
    ans = []
    np %= n
    while np < n:
        if nxt[np]+np > n:
            ans.append(a[np])
            np += 1
        elif nxt[np]+np == n:
            np = n
        else:
            np = nxt[np]+np
    print(" ".join(map(str,ans)))



    return

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

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 p=d[s]+1
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<p:break
   q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

R, C, k = (int(x) for x in input().split())
V = [[0] * (C + 5) for _ in range(R + 5)]
for _ in range(k):
    r, c, v = (int(x) for x in input().split())
    V[r][c] = v

# dp[i][j][3]
dp = [[[0] * 4 for _ in range(C + 5)] for _ in range(R + 5)]
for i in range(1, R + 3):
    for j in range(1, C + 3):
        # 行移動
        dp[i][j][0] = max(dp[i][j][0], max(dp[i - 1][j]))
        dp[i][j][1] = max(dp[i][j][1], max(dp[i - 1][j]) + V[i][j])
        for k in range(4):
            # 列移動
            if k > 0:
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k - 1] + V[i][j])
            dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
print(max(dp[R][C]))

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

R, C, k = (int(x) for x in input().split())
V = [[0] * (C + 5) for _ in range(R + 5)]
for _ in range(k):
    r, c, v = (int(x) for x in input().split())
    V[r][c] = v

# dp[3][i][j]
dp = [[[0] * (C + 5) for _ in range(R + 5)] for _ in range(4)]
for i in range(R + 3):
    for j in range(C + 3):
        for k in range(4):
            # 行移動
            dp[0][i + 1][j] = max(dp[0][i + 1][j], dp[k][i][j])
            dp[1][i + 1][j] = max(dp[1][i + 1][j], dp[k][i][j] + V[i + 1][j])
            # 列移動
            dp[k][i][j + 1] = max(dp[k][i][j + 1], dp[k][i][j])
            if k < 3:
                dp[k + 1][i][j + 1] = max(dp[k + 1][i][j + 1], dp[k][i][j] + V[i][j + 1])
print(max(dp[k][R][C] for k in range(4)))
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
H.sort()
for i in range(K):
    H = H[:-1]
print(sum(H))

### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
H.sort()
if K != 0:
    H = H[:-K]
print(sum(H))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
cands = [0]*max(a)

ans = 0
for num in a:
    if cands[num-1] >= 2:
        continue
    for i in range(num, max(a)+1, num):
        cands[i-1] += 1
        
for num in a:
    if cands[num-1]==1:
        ans+=1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
M = max(a)
cands = [0]*M

ans = 0
for num in a:
    if cands[num-1] >= 2:
        continue
    for i in range(num, M+1, num):
        cands[i-1] += 1
        
for num in a:
    if cands[num-1]==1:
        ans+=1
print(ans)
### BUGGY CODE ###

x = int(input())

def gen_divisor(x):
    for i in range(1, x + 1):
        if x % i == 0:
            yield i

def gen_candidates(limit, divisor):
    for a in range(limit):
        yield (a, a - divisor)


for divisor in gen_divisor(x):
    for a, b in gen_candidates(x + 1, divisor):
        if a**5 - b**5 == x:
            print(a, b)
            break
    else:
        continue
    break

### FIXED CODE ###

X = int(input())

for a in range(-119,119):
    for b in range(-119,119):
        if a**5 - b**5 == X:
            print(a,b)
            break
    else:
        continue
    break
### BUGGY CODE ###

def main():
    from sys import stdin
    input = stdin.readline

    h, w, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    ab_d = {a*(10**9)+b-1 for a, b in ab}

    ans = [set() for _ in range(9)]
    for a, b in ab:
        temp = [None for _ in [0]*25]
        for i in range(5):
            for j in range(5):
                if 0 < a+i-2 <= h and 0 < b+j-2 <= w:
                    if (a+i-2)*(10**9)+b+j-3 in ab_d:
                        temp[i*5+j] = 1
                    else:
                        temp[i*5+j] = 0
        for i in range(3):
            for j in range(3):
                cnt = [temp[(i+k)*5+j+l] for k in range(3) for l in range(3)]
                if None not in cnt:
                    ans[sum(cnt)-1].add((a+i-2)*(10**9)+b+j-3)

    for i in range(9):
        ans[i] = len(ans[i])

    print((h-2)*(w-2)-sum(ans))
    for i in ans:
        print(i)


main()


### FIXED CODE ###

h,w,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*n]
ab_d={a*(10**9)+b-1 for a,b in ab}

ans=[set() for _ in range(9)]
for a,b in ab:
    temp=[None for _ in [0]*25]
    for i in range(5):
        for j in range(5):
            if 0<a+i-2<=h and 0<b+j-2<=w:
                if (a+i-2)*(10**9)+b+j-3 in ab_d:
                    temp[i*5+j]=1
                else:
                    temp[i*5+j]=0
    for i in range(3):
        for j in range(3):
            cnt=[temp[(i+k)*5+j+l] for k in range(3) for l in range(3)]
            if None not in cnt:
                ans[sum(cnt)-1].add((a+i-2)*(10**9)+b+j-3)
                
for i in range(9):
    ans[i]=len(ans[i])

print((h-2)*(w-2)-sum(ans))
for i in ans:
    print(i)
### BUGGY CODE ###

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

data = []

for i in range(N):
  A,B = map(int,input().split())
  data.append([A,B])

dp = [0] * (H+1)

for i in range(1,H+1):
    dp[i] = min([dp[max(0,i-data[j][0])] + data[j][1] for j in range(N)])
    #print(dp)
print(dp[H])

### FIXED CODE ###

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

data = []

for i in range(N):
  A,B = map(int,input().split())
  data.append([A,B])

dp = [0] * (H+1)

for i in range(1,H+1):
    dp[i] = min([dp[max(0,i-data[j][0])] + data[j][1] for j in range(N)])
    #print(dp)
print(dp[H])
### BUGGY CODE ###

from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix


def main():
    def f(hi, wi):
        return hi * w + wi

    h, w = map(int, input().split())
    sh, sw = map(int, input().split())
    gh, gw = map(int, input().split())
    s = [input() for _ in range(h)]
    N = h * w

    row = []
    col = []
    cost = []

    for hi in range(h):
        for wi in range(w):
            if s[hi][wi] == "#":
                continue

            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    nh = hi + dh
                    nw = wi + dw
                    if 0 <= nh <= h - 1 and 0 <= nw <= w - 1 and s[nh][nw] == ".":
                        row.append(f(hi, wi))
                        col.append(f(nh, nw))
                        if abs(dh) + abs(dw) == 1:
                            weight = 0
                        else:
                            weight = 1
                        cost.append(weight)

    g = csr_matrix((cost, (row, col)), shape=(N, N))
    dist = dijkstra(g, indices=f(sh-1, sw-1)).astype(int)
    ans = dist[f(gh-1, gw-1)]
    ans = max(ans, -1)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():

    def f(hi, wi):
        return hi * w + wi

    h, w = map(int, input().split())
    sh, sw = map(int, input().split())
    gh, gw = map(int, input().split())

    s = [input() for _ in range(h)]
    INF = 10 ** 9

    sh -= 1
    sw -= 1
    gh -= 1
    gw -= 1

    dq = deque([f(sh, sw)])
    dist = [[INF] * w for _ in range(h)]
    dist[sh][sw] = 0

    while dq:
        i = dq.popleft()
        hi, wi = divmod(i, w)

        for dh in range(-2, 3):
            for dw in range(-2, 3):
                if dh == 0 and dw == 0:
                    continue
                nh = hi + dh
                nw = wi + dw
                if 0 <= nh <= h - 1 and 0 <= nw <= w - 1 and s[nh][nw] == ".":
                    if abs(dh) + abs(dw) == 1:
                        if dist[hi][wi] < dist[nh][nw]:
                            dist[nh][nw] = dist[hi][wi]
                            dq.appendleft(f(nh, nw))
                    else:
                        if dist[hi][wi] + 1 < dist[nh][nw]:
                            dist[nh][nw] = dist[hi][wi] + 1
                            dq.append(f(nh, nw))

    ans = dist[gh][gw]
    if ans == INF:
        ans = -1

    print(ans)


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

N = int(input())
import numpy as np
li = np.array([0]*N)
ans = 0
for i in range(N):
    li[i:N:i+1]+=1
    ans += li[i]*(i+1)
    

print(ans)

### FIXED CODE ###

N = int(input())

counter = 0
for n in range(1,N+1):
    a = N//n
    counter += a*(a+1)*n//2


print(counter)
### BUGGY CODE ###

S=input()
q=int(input())
RV=0
A="A"
for i in range(q):
    IN=input()
    if IN=="1":
        RV+=1
    else:
        t,f,c=IN.split()
        if RV%2==0:
            if f=="1":
                A=c+A               
            else:
                A=A+c
        else:
            if f=="1":
                A=A+c
            else:
                A=c+A
if RV%2==0:
    for i in range(len(A)):
        if A[i]=="A":
            print(A[:i]+S+A[i+1:])
else:
    A=A[::-1]
    for i in range(len(A)):
        if A[i]=="A":
            print(A[:i]+S[::-1]+A[i+1:])

### FIXED CODE ###

S=input()
q=int(input())
RV=0
A="A"
for i in range(q):
    IN=input()
    if IN=="1":
        RV+=1
    else:
        t,f,c=IN.split()
        if RV%2==0:
            if f=="1":
                A=c+A               
            else:
                A=A+c
        else:
            if f=="1":
                A=A+c
            else:
                A=c+A
if RV%2==0:
    for i in range(len(A)):
        if A[i]=="A":
            print(A[:i]+S+A[i+1:])
else:
    A=A[::-1]
    for i in range(len(A)):
        if A[i]=="A":
            print(A[:i]+S[::-1]+A[i+1:])
### BUGGY CODE ###

h, w=map(int, input().split())
a=[]
visited=[[True for i in range(w)] for j in range(h)]
need_visited=[[0 for i in range(w)] for j in range(h)]
stack=[]
for i in range(h):
    a.append(list(input()))

for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            stack.append([i, j])
            visited[i][j]=False



dx=[1, -1, 0, 0]
dy=[0, 0, 1, -1]


while len(stack)!=0:
    now_point=stack.pop(0)
    now_y=now_point[0]
    now_x=now_point[1]
    for i in range(4):
        if 0<=now_x+dx[i]<=w-1 and 0<=now_y+dy[i]<=h-1:
            if a[now_y+dy[i]][now_x+dx[i]]==".":
                if visited[now_y+dy[i]][now_x+dx[i]]:
                    need_visited[now_y+dy[i]][now_x+dx[i]]=need_visited[now_y][now_x]+1
                    visited[now_y+dy[i]][now_x+dx[i]]=False

                    stack.append([now_y+dy[i], now_x+dx[i]])
max_list=[]
for i in range(h):
    max_list.append(max(need_visited[i]))
print(max(max_list))


### FIXED CODE ###

from collections import deque

H, W = [int(x) for x in input().split()]
cell = [list(input()) for i in range(H)]

painted = deque()
for h in range(H):
    for w in range(W):
        if cell[h][w] == '#':
            painted.append([h, w, 0])

ans = 0
while len(painted) > 0:
    blackcell = painted.popleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = blackcell[0] + dy
        nw = blackcell[1] + dx
        d = blackcell[2]
        if 0 <= nh < H and 0 <= nw < W and cell[nh][nw] == '.':
            cell[nh][nw] = '#'
            painted.append([nh, nw, d + 1])
        ans = d

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

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

    #p_list.sort(reverse=True)
    #print(p_list)

    ans = 0
    if k == 1:
        p_list.sort(reverse=True)
        ans = (p_list[0]+1)*0.5
    else:
        for j in range(n-(k-1)):
            ans_tmp = 0
            for i in range(k):
                ans_tmp += (p_list[i+j]+1)*0.5
            if ans_tmp >= ans:
                ans = ans_tmp

    print(ans)

    

if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    
    n,k = map(int, input().split())
    
    p_list = list(map(int, input().split()))
 
    #p_list.sort(reverse=True)
    #print(p_list)
 
    ans = 0
    if k == 1:
        p_list.sort(reverse=True)
        ans = (p_list[0]+1)*0.5
    else:
        for j in range(n-(k-1)):
            if j == 0:
                ans_tmp = 0
                for i in range(k):
                    ans_tmp += (p_list[i+j]+1)*0.5
            else:
                ans_tmp -= (p_list[(j-1)]+1)*0.5
                ans_tmp += (p_list[k+(j-1)]+1)*0.5
            
            
            if ans_tmp >= ans:
                ans = ans_tmp
 
    print(ans)
 
    
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import deque

n, x, y = map(int, input().split())
eage = [[] for _ in range(n)]

for i in range(n-1):
  eage[i].append( i+1 )
  eage[i+1].append( i )

x -= 1
y -= 1

eage[x].append( y )
eage[y].append( x )

visited = [[-1] * n for _ in range(n)]

for start_point in range(n):
  visited[start_point][start_point] = 0
  # [0] とか [0, 2, 3] とか [1, 3]
  q = deque([start_point])
  while q:
    v = q.popleft()
    for j in eage[v]:
      # 未訪問
      if visited[start_point][j] == -1:
        # v が start_point の切り替え役
        visited[start_point][j] = visited[start_point][v] + 1
        q.append( j )

from itertools import chain

counter = [0] * n

for v in list(chain.from_iterable(visited)):
  counter[v] += 1

for ans in counter[1:]:
  print(ans // 2)


### FIXED CODE ###

from collections import deque

n, x, y = map(int, input().split())
eage = [[] for _ in range(n)]

for i in range(n-1):
  eage[i].append( i+1 )
  eage[i+1].append( i )

x -= 1
y -= 1

eage[x].append( y )
eage[y].append( x )

visited = [[-1] * n for _ in range(n)]

counter = [0] * n
for start_point in range(n):
  visited[start_point][start_point] = 0
  # [0] とか [0, 2, 3] とか [1, 3]
  q = deque([start_point])
  while q:
    v = q.popleft()
    for j in eage[v]:
      # 未訪問
      if visited[start_point][j] == -1:
        # v が start_point の切り替え役
        visited[start_point][j] = visited[start_point][v] + 1
        q.append( j )
  for c in visited[start_point]:
    counter[c] += 1

for ans in counter[1:]:
  print(ans // 2)
### BUGGY CODE ###

n,m,p = map(int, input().split())
edge = []
e1 = [list() for _ in range(n+1)]
for _ in range(m):
  a,b,c = map(int, input().split())
  edge.append((a,b,p-c))
  e1[a].append(b)
dis = [float("inf")]*(n+1)
dis[1] = 0
t = []
for i in range(n):
  for a,b,c in edge:
    if dis[b] > dis[a] + c:
      dis[b] = dis[a] + c
      if i == n-1:
        t.append(b)
s = set(t)
while t:
  v = t.pop()
  for x in e1[v]:
    if x == n:
      print(-1)
      exit(0)
    if x in s:
      continue
    s.add(x)
    t.append(x)
print(max(0,-dis[n]))


### FIXED CODE ###

n,m,p = map(int, input().split())
edge = []
e1 = [list() for _ in range(n+1)]
for _ in range(m):
  a,b,c = map(int, input().split())
  edge.append((a,b,p-c))
  e1[a].append(b)
dis = [float("inf")]*(n+1)
dis[1] = 0
t = []
for i in range(n):
  for a,b,c in edge:
    if dis[b] > dis[a] + c:
      dis[b] = dis[a] + c
      if i == n-1:
        t.append(b)
s = set(t)
while t:
  v = t.pop()
  for x in e1[v]:
    if x == n:
      print(-1)
      exit(0)
    if x in s:
      continue
    s.add(x)
    t.append(x)
print(max(0,-dis[n]))
### BUGGY CODE ###

import sys
from collections import Counter
import random
import time
import math

def comb(n, r):
    return (math.factorial(n)//(math.factorial(n-r)*math.factorial(r)))

n=int(input())
a=list(map(int,input().split()))
S=[sum(a[:i])for i in range(n+1)]
s=set(S)
c=0
for i in s:
    nu=S.count(i)
    if(nu>1):c+=comb(nu,2)
print(c)

### FIXED CODE ###

import sys
from collections import Counter
import random
import numpy as np
import time

n=int(input())
a=list(map(int,input().split()))
S=[0]
for i in range(n):
    S.append(S[i]+a[i])
    
S.sort()
c=0
ch=0
for i in range(len(S)-1):
    if(S[i]!=S[i+1]):
        ch+=1
        c+=(ch*(ch-1))//2
        ch=0
    else:ch+=1
if(ch!=0):
    ch+=1
    c+=(ch*(ch-1))//2
print(c)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
tmp = [a[0]]
for i in range(1, n):
  if sum(tmp) > sum(a) / 2:
    break
  tmp.append(a[i])
print(min(sum(tmp) * 2 - sum(a), sum(a) - sum(tmp[:-1]) * 2))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
sm = sum(a)
tmp = a[0]
for i in range(1, n):
  if tmp > sm / 2:
    print(min(tmp * 2 - sm, sm - (tmp - a[i-1]) * 2))
    break
  tmp += a[i]
else:
  print(sm - (tmp - a[i]) * 2)
### BUGGY CODE ###

from sys import stdin

if __name__ == '__main__':
    n = stdin.readline()
    n, K = n.split(' ')
    n = int(n)
    K = int(K)
    arr = stdin.readline()
    arr = [int(a) for a in arr.split(' ')]
    dp = [float('inf')]*n
    dp[0] = 0
    for i in range(n):
        for k in range(1, K+1):
            if i - k < 0:
                break
            dp[i] = min(dp[i], dp[i-k]+abs(arr[i]-arr[i-k]))
    print(dp[-1])

### FIXED CODE ###

def main():
    infinity = 1e10

    n, k, height = getInputs()

    cost = [infinity] * n
    cost[0] = 0
    cost[1] = abs(height[0] - height[1])

    for i in range(2, n):
        for j in range(i - 1, i - k - 1, -1):
            if j >= 0:
                cost[i] = min(cost[i], cost[j] + abs(height[i] - height[j]))

    print(cost[-1])

def getInputs():
    n, k = map(lambda x: int(x), input().split())
    height = tuple(map(lambda x: int(x), input().split()))

    return n, k, height

main()
### BUGGY CODE ###

def resolve():
    N = int(input())
    S = input()
    ans = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            if S[i] == S[j]:
                continue
            for k in range(j+1, N):
                if (j - i) == (k  - j):
                    continue
                if S[i] != S[k] and S[j] != S[k]:
                    ans += 1
    print(ans)
resolve()

### FIXED CODE ###

from collections import Counter

N = int(input())
s = input()
cnt = Counter(s)
R = cnt.get('R', 0)
G = cnt.get('G', 0)
B = cnt.get('B', 0)
ans = R * G * B
for i in range(N-1):
  for j in range(i+1, N):
    if s[i] != s[j] and 2*j-i < N and s[i] != s[2*j-i] and s[j] != s[2*j-i]:
      ans -= 1
print(ans)