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


def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def main():

    N = int(input())
    A = [int(input()) for i in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = dp_table(N, sum_A + 1)
    # dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

    # init
    dp[0][A[0]] = 1
    dp[0][0] = 2  # 他の色のうちどちらに入れるかで2通り

    # init2
    dp2 = dp_table(N, sum_A+1)  # ある二色でsum_Aを等分するパターンを数える
    dp2[0][A[0]] = 1
    dp2[0][0] = 1  # 今度は片方に集中したパターン

    # dp
    for i in range(1, N):
        for length in range(0, sum_A + 1):
            # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
            if length >= A[i]:
                dp[i][length] = dp[i - 1][length - A[i]] + dp[i - 1][length] * 2
            else:
                dp[i][length] = dp[i-1][length]*2
            dp[i][length] %= mod
            if length >= A[i]:
                dp2[i][length] = dp2[i - 1][length - A[i]] + dp2[i - 1][length]
            else:
                dp2[i][length] = dp2[i-1][length]
            dp2[i][length] %= mod
    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###


def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def main():

    N = int(input())
    A = [int(input()) for _ in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = [[0] * (sum_A+1) for i in range(N)]
    # dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

    # init
    dp[0][A[0]] = 1
    dp[0][0] = 2  # 他の色のうちどちらに入れるかで2通り

    # init2
    dp2 = [[0] * (sum_A+1) for i in range(N)]  # ある二色でsum_Aを等分するパターンを数える
    dp2[0][A[0]] = 1
    dp2[0][0] = 1  # 今度は片方に集中したパターン

    # dp
    sum_now = A[0]
    for i in range(1, N):
        a = A[i]
        sum_now += a
        for length in range(sum_now+1):
            # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
            if length >= a:
                dp[i][length] = dp[i - 1][length - a] + \
                    (dp[i - 1][length] << 1)
            else:
                dp[i][length] = dp[i-1][length] << 1
            dp[i][length] %= mod

        for length in range(min(sum_now + 1, sum_A // 2 + 1)):
            if length >= a:
                dp2[i][length] = dp2[i - 1][length - a] + dp2[i - 1][length]
            else:
                dp2[i][length] = dp2[i-1][length]
            dp2[i][length] %= mod
    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


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

from collections import defaultdict
h, w, m = map(int, input().split())
hw = [tuple(map(int, input().split())) for _ in range(m)]
tate, yoko = defaultdict(int), defaultdict(int)
for h, w in hw:
    tate[h] += 1
    yoko[w] += 1
tate = sorted(tate.items(), key=lambda x:x[1], reverse=True)
yoko = sorted(yoko.items(), key=lambda x:x[1], reverse=True)
tate_max, yoko_max = tate[0][1], yoko[0][1]
max_tates, max_yokos = [], []
for t in tate:
    if t[1] == tate_max:
        max_tates.append(t)
    else:
        break
for y in yoko:
    if y[1] == yoko_max:
        max_yokos.append(y)
    else:
        break

for ta in max_tates:
    for yo in max_yokos:
        if (ta[0], yo[0]) not in hw:
            print(tate_max + yoko_max)
            exit()
print(tate_max + yoko_max - 1)

### FIXED CODE ###

from collections import defaultdict
h, w, m = map(int, input().split())
hw = [tuple(map(int, input().split())) for _ in range(m)]
tate, yoko = defaultdict(int), defaultdict(int)
for h, w in hw:
    tate[h] += 1
    yoko[w] += 1
tate = sorted(tate.items(), key=lambda x:x[1], reverse=True)
yoko = sorted(yoko.items(), key=lambda x:x[1], reverse=True)
tate_max, yoko_max = tate[0][1], yoko[0][1]
max_tates, max_yokos = [], []
for t in tate:
    if t[1] == tate_max:
        max_tates.append(t)
    else:
        break
for y in yoko:
    if y[1] == yoko_max:
        max_yokos.append(y)
    else:
        break

hw = set(hw)
for ta in max_tates:
    for yo in max_yokos:
        if (ta[0], yo[0]) not in hw:
            print(tate_max + yoko_max)
            exit()
print(tate_max + yoko_max - 1)
### BUGGY CODE ###

N = int(input())
H = [int(h) for h in input().split()]

max = 0
i = 0
while i < len(H):
    count = 0
    for j in range(i, len(H)-1):
        if H[j] >= H[j+1]:
            count += 1
        else:
            i = j
            break
    if count > max:
        max = count
    i += 1

print(max)

### FIXED CODE ###

N = int(input())
H = [int(h) for h in input().split()]

max = 0
count = 0
for i in range(len(H)-1):
    if H[i] >= H[i+1]:
        count += 1
    else:
        if count > max:
            max = count
        count = 0
if count > max:
    max = count
print(max)
### BUGGY CODE ###


#readed editional
MOD = int(1e9)+7
#print(MOD)
S = [int(x) if x != '?' else - 1 for x in input()]

n = len(S)

dp = [[0]*13 for i in range(n+1)]

dp[0][0] = 1
#print(dp)

for i in range(n):
    c = S[i]
    for j in range(10):
        if (c != -1 and c!= j):
            continue
        for ki in range(13):
            dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki]
    
    for j in range(13):
        dp[i+1][j] %= MOD

#print(S)
#print(dp)
print(dp[len(dp)-1][5])


### FIXED CODE ###


#readed editional
MOD = int(1e9)+7
#print(MOD)
S = [int(x) if x != '?' else - 1 for x in input()]

n = len(S)

dp = [[0]*13 for i in range(n+1)]

dp[0][0] = 1
#print(dp)

for i in range(n):
    c = S[i]
    if c == -1:
        for j in range(10):
            for ki in range(13):
                dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki]
    else:
        for ki in range(13):
            dp[i + 1][(ki * 10 + c) % 13] += dp[i][ki]        
    for j in range(13):
        dp[i+1][j] %= MOD

#print(S)
#print(dp)
print(dp[len(dp)-1][5])
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC68 C

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

ab = [list(map(int,input().split())) for _ in range(m)]
s = [ab[i][1] for i in range(m) if ab[i][0] == 1]
g = [ab[i][0] for i in range(m) if ab[i][1] == n]
f = 0
s.sort()
s.reverse()
g.sort()
for i in s:
    if i in g:
        f = 1
        break
if f:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')


### FIXED CODE ###

#!/usr/bin/env python3
#ABC68 C

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

s = [0]*(200000+1)
g = [0]*(200000+1)
for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        s[b] += 1
    if b == n:
        g[a] += 1
f = 0
for i in range(200000+1):
    if s[i] & g[i]:
        f = 1
        break
if f:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

#
# 179C
#
n = input()
n = int(n)

c = 0
for i in range(n):
    j = i+1
    k = 1
    while True:
        if j*k<n:
            c = c+1
        else:
            break
        k = k+1

print(c)

### FIXED CODE ###

#
# 179C
#
n = input()
n = int(n)

c = 0
for i in range(n):
    j = i+1
    k = 1
    while True:
        if j*k<n:
            c = c+1
        else:
            break
        k = k+1

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

n = int(input())
a = map(int,input().split())
ans = 1
for i in sorted(a):
    ans = ans*i
    if ans == 0:
        break
if ans <= 10 ** 18:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

n = int(input())
a = map(int,input().split())
ans = 1
for i in sorted(a):
    ans = ans*i
    if ans == 0:
        print(0)
        exit()
    elif ans > 10 ** 18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N, M = rl()
E = defaultdict(list)
for i in range(M):
	u, v = rl()
	E[u-1].append(v-1)
	#E[v-1].append(u-1)
S, T = rl()
S -= 1
T -= 1

dp = [[float('inf')]*3 for i in range(N)]

def dfs(n, d):
	for m in E[n]:
		r = (d+1)%3
		if dp[m][r] > d+1:
			dp[m][r] = d+1
			dfs(m, d+1)

dfs(S, 0)
if dp[T][0] != float('inf'):
	print(dp[T][0]//3)
else:
	print(-1)


### FIXED CODE ###

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N, M = rl()
E = defaultdict(list)
for i in range(M):
	u, v = rl()
	E[u-1].append(v-1)
S, T = rl()
S -= 1
T -= 1

dp = [[float('inf')]*3 for i in range(N)]

heap = []
heappush(heap, (0, S, 0))
while heap:
	d, n, r = heappop(heap)
	if n == T and r == 0:
		continue
	#if dp[n][r] != d:
	#	continue
	nr = (d+1)%3
	for m in E[n]:
		if dp[m][nr] > d+1:
			dp[m][nr] = d+1
			heappush(heap, (d+1, m, nr))

if dp[T][0] != float('inf'):
	print(dp[T][0]//3)
else:
	print(-1)
### BUGGY CODE ###

from copy import deepcopy
import queue

def shortestpath(y0, x0):
    copymaze = deepcopy(maze)
    step_cnt = [[-1] * w for _ in range(h)]
    step_cnt[y0][x0] = 0
    q = queue.Queue()
    q.put((y0, x0))
    while not q.empty():
        y, x = q.get()
        copymaze[y][x] = '#'
        for i in range(4):
            y_next = y + dy[i]
            x_next = x + dx[i]
            if 0 <= y_next < h and 0 <= x_next < w and copymaze[y_next][x_next] == '.':
                q.put((y_next, x_next))
                step_cnt[y_next][x_next] = step_cnt[y][x] + 1
                    
    return step_cnt[y][x]

h, w = map(int, input().split())      
maze = [[x for x in input()] for _ in range(h)]
dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]

max_steps = -1
for y0 in range(h):
    for x0 in range(w):
        if maze[y0][x0] != '#':
            max_steps = max(max_steps, shortestpath(y0, x0))

print(max_steps)

### FIXED CODE ###

import queue

def shortestpath(y0, x0):
    step_cnt = [[-1] * w for _ in range(h)]
    step_cnt[y0][x0] = 0
    q.put((y0, x0))
    while not q.empty():
        y, x = q.get()
        for i in range(4):
            y_next = y + dy[i]
            x_next = x + dx[i]
            if 0 <= y_next < h and 0 <= x_next < w\
            and maze[y_next][x_next] == '.'\
            and step_cnt[y_next][x_next] == -1:
                q.put((y_next, x_next))
                step_cnt[y_next][x_next] = step_cnt[y][x] + 1
                    
    return step_cnt[y][x]

h, w = map(int, input().split())      
maze = [[x for x in input()] for _ in range(h)]
dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]
q = queue.Queue()

max_steps = -1
for y0 in range(h):
    for x0 in range(w):
        if maze[y0][x0] != '#':
            max_steps = max(max_steps, shortestpath(y0, x0))

print(max_steps)
### BUGGY CODE ###

def main(N,h,K):
    inf = 2**31 - 1
    dp = [inf] * N
    dp[0] = 0
    for i in range(N-1):
        for k in range(1, K+1):
            if i+k < N:
                dp[i+k] = min(dp[i+k], dp[i] + abs(h[i] - h[i+k]))
            else:
                break
    return dp[N-1]

N, K = map(int, input().split())
h = list(map(int, input().split()))

print(main(N,h,K))

### FIXED CODE ###

def main2(N,h,K):
    dp = [0] * N
    for i in range(1,N):
        dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(max(0, i-K), i)])
    return dp[-1]

N, K = map(int, input().split())
h = list(map(int, input().split()))
print(main2(N,h,K))
### BUGGY CODE ###

import numpy as np
N,M = map(int,input().split())

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

count = 0

for c in range(1,M+1):
    b = c - a*0.5
    b = b % a
    if sum(b) == 0:
        count += 1

print(count)


### FIXED CODE ###

# 最大公約数を返す
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
 
# 最小公倍数を返す
def lcm(a, b):
    return a * b // gcd(a, b)

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

# ループを回しながら最小公倍数を計算していく
# 与えられたN個の偶数はすべて２で割っていく
leastCommonMultiple = L[0] // 2
for i in range(N):
    L[i] //= 2
    leastCommonMultiple = lcm(leastCommonMultiple, L[i])

# フラグ
c = 0

# Lに格納されているＮ個の数に含まれる素因数２の数が同じかどうかチェックする
while True:

    for i in range(N):
        # ２で割り切れない場合
        # L[i]に含まれている数すべてが２で割り切れないならＯＫ
        if L[i] % 2 == 1:
            c += 1
        # ２で割り切れるなら、２で割った数で上書き
        else:
            L[i] //= 2

    if not c == 0:
        break


if c == N:
    print( ((M // leastCommonMultiple) + 1) // 2 )
else:
    print(0)
### BUGGY CODE ###

from numpy import *
N,K = map(int,input().split())
P = list(map(int,input().split()))
Q = (N-K+1)*[0]

for n in range(N-K+1):
  Q[n] = sum(P[n:n+K])

R = argmax(Q)
print(0.5*(sum(P[R:R+K])+K))

### FIXED CODE ###

from numpy import *
N,K = map(int,input().split())
P = list(map(int,input().split()))
Q = (N-K+1)*[0]
R = sum(P[0:K])
Q[0] = R

for n in range(1,N-K+1):
  R+=P[n-1+K]-P[n-1]
  Q[n] = R

S = argmax(Q)
print(0.5*(sum(P[S:S+K])+K))
### BUGGY CODE ###

N=int(input())
A = []
ans =[]
for i in range(N):
    new = int(input())
    if new not in ans:
        ans.append(new)

    else:
        ans.remove(new)


print(len(ans))


### FIXED CODE ###

N=int(input())
A = []

for i in range(N):
    new = int(input())
    A.append(new)

A.sort()
A.append(0)

start=A[0]
cnt=1
anscnt=0

for i in range(1,len(A)):

    if A[i]==start:
        cnt+=1
    elif A[i]!=start:
        if cnt%2==0:
            anscnt+=cnt
        elif cnt%2!=0:
            anscnt+=cnt-1    
        cnt=1
        start=A[i]


print(N-anscnt)
### BUGGY CODE ###

S = input()
p = 10 ** 9 + 7
DP = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
DP[0][0] = 1
M = [[0 for _ in range(13)] for _ in range(6)]
for i in range(6):
  for j in range(10):
    M[i][j] = j * 10 ** i % 13
for i, s in enumerate(S[::-1]):
  if s == '?':
    for j in range(10):
      m = M[i % 6][j]
      for k in range(13):
        DP[i + 1][(k + m) % 13] += DP[i][k]
  else:
    m = M[i % 6][int(s)]
    for k in range(13):
      DP[i + 1][(k + m) % 13] += DP[i][k]
  for k in range(13):
    DP[i + 1][k] %= p
print(DP[-1][5])

### FIXED CODE ###

S = input()
p = 10 ** 9 + 7
DP = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
DP[0][0] = 1
M = [[0 for _ in range(13)] for _ in range(6)]
for i in range(6):
  for j in range(10):
    M[i][j] = j * 10 ** i % 13
for i, s in enumerate(S[::-1]):
  if s == '?':
    for j in range(10):
      m = M[i % 6][j]
      for k in range(13):
        DP[i + 1][(k + m) % 13] += DP[i][k]
  else:
    m = M[i % 6][int(s)]
    for k in range(13):
      DP[i + 1][(k + m) % 13] += DP[i][k]
  for k in range(13):
    DP[i + 1][k] %= p
print(DP[-1][5])
### BUGGY CODE ###

import sys
import os

MOD = 2019


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    L, R = list(map(int, sys.stdin.readline().split()))
    ret = float('inf')
    for i in range(L, R):
        for j in range(L + 1, R + 1):
            ret = min(ret, (i * j) % MOD)

    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os

MOD = 2019


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    L, R = list(map(int, sys.stdin.readline().split()))
    ret = float('inf')

    if R - L >= 2019:
        print(0)
        exit()

    for i in range(L, R+1):
        for j in range(i+1, R+1):
            ret = min(ret, (i * j) % MOD)

    print(ret)


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

class SegTree():
    def __init__(self, N, e=float("inf"), operator_func=min):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x

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

tree = SegTree(N, e=set(), operator_func=lambda x,y:set(x)|set(y))
tree.set_list(S)

Q = int(input())
for _ in range(Q):
    mode, i, v = input().split()
    if mode=="1":
        i = int(i)-1
        tree.update(i, set(v))
    else:
        i = int(i)-1
        v = int(v)
        print(len(tree.get(i, v)))

### FIXED CODE ###

import sys
from operator import or_
input=sys.stdin.readline


class SegTree():
    def __init__(self, N, e=float("inf"), operator_func=min):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x


def main():
    N = int(input())
    S = list(input())[:-1]
    trees = {chr(97+i):SegTree(N, e=False, operator_func=or_) for i in range(26)}

    for i, s in enumerate(S):
        trees[s].update(i, True)

    Q = int(input())
    for _ in range(Q):
        mode, i, v = input().split()
        if mode=="1":
            i = int(i)-1
            trees[S[i]].update(i, False)
            trees[v].update(i, True)
            S[i] = v
        else:
            i = int(i)-1
            v = int(v)
            ans = 0
            for j in range(26):
                ans += trees[chr(97+j)].get(i, v)
            print(ans)


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

n = int(input())
a = [int(input()) for i in range(n)]
m = max(a)
for j in range(n):
	if a[j] < m:
		print(m)
	elif a[j] == m:
		if a.count(m) > 1:
			print(m)
		else:
			b = a[:]
			b[j] = 0
			print(max(b))
	else:
		b = a[:]
		b[j] = 0
		print(max(b))

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
m1 = max(a)
c = a.count(m1)
if len(set(a)) == 1:
	for i in range(n):
		print(m1)
else:
	m2 = sorted(set(a))[-2]
	for i in range(n):
		if a[i] < m1:
			print(m1)
		elif a[i] == m1:
			if c > 1:
				print(m1)
			else:
				print(m2)
		else:
			print(m2)
### BUGGY CODE ###

N = 50000
t = [1]*N
p = []
for i in range(3, N + 1, 2):
    if t[i]:
        p.append(i)
        for j in range(3*i, N+1, 2*i): t[j] = 0

while True:
    n = int(input())
    if n == 0: break

    if n % 2:
        print(1 if n - 2 in p else 0)
    else:
        count = 0
        for p1 in p:
            if 2*p1 > n: break
            if n - p1 in p: count += 1
        print(count)

### FIXED CODE ###

import sys

N = 50000
t = [1]*(N)
p = [2]
d = {2:1}
for i in range(3, N, 2):
    if t[i]:
        p.append(i)
        d[i] = 1
        for j in range(3*i, N, 2*i): t[j] = 0

while True:
    n = int(sys.stdin.readline())
    if n == 0: break

    count = 0
    if n % 2:
        if n - 2 in p: count += 1
    else:
        for p1 in p:
            if 2*p1 > n: break
            if n - p1 in d:
                count += 1
    print(count)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 0
ans += a.count(0)
for i in range(2,n+1):
    tmp = []
    x = 0
    for j in range(i):
        x += a[j]
    if x == 0:
        ans += 1
    for k in range(n - i):
        x += a[k + i] - a[k]
        if x == 0:
            ans += 1
print(ans)        


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0]
for i in range(n):
    x = 0
    x += b[i] + a[i]
    b.append(x)
b.sort()
check = b[0]
count = 1
ans = 0
for i in range(1,n+1):
    if b[i] == check:
        count += 1
    else:
        ans += count * (count - 1) // 2
        check = b[i]
        count = 1
ans += count * (count - 1) // 2            
print(ans)
### BUGGY CODE ###

N = int(input())
An = [int(n) for n in input().split()]
M = sorted(set(An))
mini=M[0]
for i,x in enumerate(M):
    M = [mini] + [x for x in M[1:] if x % mini != 0]
            
while len(M) > 1:
    if 1 in M:
        mini=1
        break
    M = [M[0]] + [x-mini for x in M[1:]]
    M.sort()
    while M[0]<1:
        M.pop(0)
    mini = min(mini,M[0])
print(mini)    


### FIXED CODE ###

N = int(input())
An = [int(n) for n in input().split()]
M = sorted(set(An))
mini=M[0]
            
while len(M) > 1:
    M = [mini] + [x%mini for x in M[1:] if x % mini != 0]
    M.sort()
    if 1 in M:
        mini=1
        break
    mini = min(mini,M[0])
print(M[0])
### BUGGY CODE ###

X,Y,Z,K = map(int, input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
array = []

for a in A:
  for b in B:
    for c in C:
      array.append(a+b+c)

array.sort()
array.reverse()
for i in range(K):
  print(array[i])

### FIXED CODE ###

from heapq import heappop, heappush,heapify
X,Y,Z,K = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
H = []
heappush(H,[-1*(A[0]+B[0]+C[0]),0,0,0])
count = 1
memo = []
while H and count <= K:
  tmp,i,j,k = heappop(H)
  print(-1*tmp)
  count += 1
  if i+1 < X and ((i+1,j,k) not in memo):
    heappush(H,[-1*(A[i+1]+B[j]+C[k]),i+1,j,k])
    memo.append((i+1,j,k))
  if j+1 < Y and ((i,j+1,k) not in memo):
    heappush(H,[-1*(A[i]+B[j+1]+C[k]),i,j+1,k])
    memo.append((i,j+1,k))
  if k+1 < Z and ((i,j,k+1) not in memo):
    heappush(H,[-1*(A[i]+B[j]+C[k+1]),i,j,k+1])
    memo.append((i,j,k+1))