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

from collections import Counter
class Combination:
    _maxNum = 0
    _divider = 0
    _fact = []
    _inv = []
    _finv = []

    def __init__(self, maxNum, divider):
        self._maxNum = maxNum
        self._divider = divider
        self._fact = [0] * (self._maxNum + 1)
        self._fact[0] = self._fact[1] = 1

        if self._divider != 0:
            self._inv = [0] * (self._maxNum + 1)
            self._finv = [0] * (self._maxNum + 1)
            self._inv[0] = self._inv[1] = self._finv[0] = self._finv[1] = 1

        for i in range(2, self._maxNum + 1):
            self._fact[i] = self._fact[i - 1] * i;
            if self._divider != 0:
                self._fact[i] %= self._divider
                self._inv[i] = self._divider - self._inv[self._divider % i] * (self._divider // i) % self._divider
                self._finv[i] = self._finv[i - 1] * self._inv[i] % self._divider

    def nPk(self, n, k):
        if(k > self._maxNum) or (n > self._maxNum) or (k > n) or (k < 0) or (n < 0):
            return 0
        return(self._fact[n] // self._fact[n - k])

    def nCk(self, n, k):
        ans = 0
        if(k > self._maxNum) or (n > self._maxNum) or (k > n) or (k < 0) or (n < 0):
            ans = 0
        elif self._divider == 0:
            ans = self.nPk(n, k)
            ans //= self._fact[k]
        else:
            ans = self._fact[n] * (self._finv[k] * self._finv[n - k] % self._divider) % self._divider

        return ans

def ABC137C_GreenBin():
    N = int(input().strip())

    di = Counter()
    for i in range(N):
        sl = sorted(input().strip())
        s = ""
        for c in sl:
            s += c    

        di[s] += 1
    
    cmb = Combination(N, 0)

    ans = 0
    for num in di.values():
        ans += cmb.nCk(num, 2)

    print(ans)


def main():
    ABC137C_GreenBin()

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import Counter

def ABC137C_GreenBin():
    N = int(input().strip())
    S = [input().strip() for i in range(N)]

    ans = 0
    di = Counter()
    for s in S:
        s = ''.join(sorted(list(s)))
        
        if s in di:
            ans += di[s]

        di[s] += 1
    
    print(ans)


def main():
    ABC137C_GreenBin()

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

def solve(w,v,tv,W):
    dp=[float('inf')]*(tv+1)
    dp[0]=0
    for i in range(len(w)):
        for j in range(tv-v[i],-1,-1):
            dp[j+v[i]]=min(dp[j+v[i]],dp[j]+w[i])
    maxx=0
    for i in range(tv+1):
        if dp[i]<=W:
            maxx=max(maxx,i)
    return maxx
if __name__=='__main__':
    n,W=map(int,input().split())
    w=[]
    v=[]
    for i in range(n):
        p,q=map(int,input().split())
        w.append(p)
        v.append(q)
    print(solve(w,v,sum(v),W))

### FIXED CODE ###

def solve(w,v,tv,W):
    dp=[float('inf')]*(tv+1)
    dp[0]=0
    for i in range(len(w)):
        for j in range(tv-v[i],-1,-1):
            dp[j+v[i]]=min(dp[j+v[i]],dp[j]+w[i])
    maxx=0
    for i in range(tv+1):
        if dp[i]<=W:
            maxx=max(maxx,i)
    return maxx
if __name__=='__main__':
    n,W=map(int,input().split())
    w=[]
    v=[]
    for i in range(n):
        p,q=map(int,input().split())
        w.append(p)
        v.append(q)
    print(solve(w,v,sum(v),W))
### BUGGY CODE ###

n=int(input())
tmp=[list(map(int,input().split())) for i in range(n)]
tmp.reverse()
tmp.append([0,0])
v=[0]
for i in range(0,n):
    cnt=0
    while(tmp[i][0]%tmp[i][1]!=0):
        cnt+=1
        tmp[i][0]+=1
    v.append(cnt)
    tmp[i + 1][0] += sum(v)
print(sum(v))



### FIXED CODE ###

n=int(input())
A=[]
B=[]
for i in range(n):
    a,b=input().split()
    A.append(a)
    B.append(b)
A.reverse()
B.reverse()
A.append(0)
B.append(0)
A=list(map(int,A))
B=list(map(int,B))

x=0
for i in range(0,n):
    cnt=0
    if A[i]%B[i]!=0:
        cnt+=(B[i]-A[i]%B[i])
        A[i]+=(B[i]-A[i]%B[i])
    x+=cnt
    A[i+1]+= x
print(x)
### BUGGY CODE ###

import heapq 
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [[i, 2] for i in a]
for _ in range(k):
    p = a.index(max(a))
    if b[p][0]%b[p][1] == 0:
        a[p] = b[p][0]//b[p][1]
    else:
        a[p] = b[p][0]//b[p][1] +1
    b[p][1] += 1
print(max(a))

### FIXED CODE ###

n, k = map(int, input().split())
a = [i-1 for i in map(int, input().split())]

left, right = 0, 10**9
while left < right:
    middle = (left+right)//2
    if middle==0:
        left=1
        break
    count = 0
    for i in a:
        count += i//middle
    
    if count <= k:
        right = middle
    else:
        left = middle + 1

print(left)
### BUGGY CODE ###

def resolve():
	# N: 品物の個数、W: 容量の上限
	N, W = map(int, input().split())
	# DP配列の宣言: DP[N][W] = 0
	dp = [[0] * (W+1) for _ in range(N+1)]
	for i in range(N):
		w_n, v_n = map(int, input().split())
		for j in range(w_n):
			dp[i+1][j] = dp[i][j]
		for j in range(w_n, W+1):
			dp[i+1][j] = max(
				dp[i][j-w_n]+v_n,	# バッグに入れた時の価値
				dp[i][j]			# バッグにいれない時の価値
			)
	print(dp[N][W])
resolve()

### FIXED CODE ###

import numpy as np
def resolve():
	# N: 品物の個数、W: 容量の上限
	N, W = map(int, input().split())
	# DP配列の宣言: DP[N][W]
	dp = np.empty((N+1, W+1), dtype=np.int64)
	# DP配列の初期化
	dp[0,:] = 0
	for i in range(N):
		w_n, v_n = map(int, input().split())
		dp[i+1, :w_n] = dp[i, :w_n]
		dp[i+1, w_n:] = np.maximum(
			dp[i, w_n:],
			dp[i, :(W+1-w_n)] + v_n
		)
	print(dp[N, W])
resolve()
### BUGGY CODE ###

# coding: utf-8
# Your code here!

n = int(input())
aa = input()
for i in range(n):
    a = aa.split()

result = 1
for i in range(n):
    result *= int(a[i])

if(result > 1000000000000000000):
    print(-1)
else:
    print(result)


### FIXED CODE ###


import sys
n = int(input())
aa = input()
a = aa.split()

for i in range(n):
    if(int(a[i]) == 0):
        print(0)
        sys.exit()

result = 1
for i in range(n):
    result *= int(a[i])
    if(result > 1000000000000000000):
        print(-1)
        sys.exit()

print(result)
### BUGGY CODE ###

N = int(input())


for i in range(1, N+1):
    sum = 0

    range_x = int((i-5)**0.5)+1 if i-5 >0 else 0
    s = set()
    for x in range(1, range_x):
        if x in s:
            continue
        range_y = int((i-x**2-x-3)**0.5)+1 if i-x**2-2*x-2 > 0 else 0
        for y in range(1, range_y):
            if y in s:
                continue
            range_z = int((i-x**2-y**2-x*y-x-y)**0.5)+1 if i-x**2-y**2-x*y-x-y > 0 else 0
            for z in range(1, range_z):
                if z in s:
                    continue
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == i:
                    num = len(set([x,y,z]))
                    sum += 6 if num == 3 else 3 if num==2 else 1
                    s.add(x)
                    s.add(y)
                    s.add(z)
                    break

    print(sum)

### FIXED CODE ###

N = int(input())

ans = [0]*(10**4+1)

for x in range(1, 10**2):
    for y in range(1, 10**2):
        for z in range(1, 10**2):
            n = x**2+y**2+z**2+x*y+y*z+z*x
            if n <10**4+1:
                ans[n] += 1

for i in range(1, N+1):
    print(ans[i])
### BUGGY CODE ###

n = int(input())
s = []
ctr = 0

for _ in range(n):
    si = input()
    slist = sorted(list(si))
    for i in range(len(s)):
        if slist == sorted(list(s[i])):
            ctr += 1
    s.append(si)

print(ctr)

### FIXED CODE ###

n = int(input())
num_of_anagram = dict()
ans = 0

for _ in range(n):
    s = input()
    s = ''.join(sorted(list(s)))
    if s in num_of_anagram:
        num_of_anagram[s] += 1
        ans += num_of_anagram[s]
    else:
        num_of_anagram[s] = 0

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

import sys
input = sys.stdin.readline
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

"""
(駅、会社)を頂点にグラフを持つ。頂点数O(M)。
そのまま辺を貼ると辺が多くなりすぎる。
(駅、会社) -> (駅、無属性) -> (駅、会社)
"""

N,M = map(int,input().split())
PQC = [[int(x) for x in input().split()] for _ in range(M)]

U = 10 ** 6

V = set(range(1,N+1))
V |= set(p + c * U for p,q,c in PQC)
V |= set(q + c * U for p,q,c in PQC)
V = tuple(V)
v_to_i = {v:i for i,v in enumerate(V)}

# グラフを作成
rows, cols = [],[]
rows += [i for i,pc in enumerate(V) if pc > U]
cols += [v_to_i[pc % U] for i,pc in enumerate(V) if pc > U]
wt = [1] * len(rows)
rows += [v_to_i[p + c * U] for p,q,c in PQC]
cols += [v_to_i[q + c * U] for p,q,c in PQC]
wt += [0] * M

graph = csr_matrix((wt, (rows, cols)), (len(V), len(V)))

start = v_to_i[1]
goal = v_to_i[N]

dist = dijkstra(graph, directed = False, indices = start)[goal]

answer = -1 if dist == float('inf') else int((dist + 1)//2)
print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict

"""
(駅、会社)を頂点にグラフを持つ。頂点数O(M)。
そのまま辺を貼ると辺が多くなりすぎる。
(駅、会社) -> (駅、無属性) -> (駅、会社)
"""

L = 32
mask = (1 << L) - 1
N,M = map(int,input().split())
graph = defaultdict(list)
for _ in range(M):
    p,q,c = map(int,input().split())
    p <<= L
    q <<= L
    graph[p].append(p+c)
    graph[p+c].append(p)
    graph[q].append(q+c)
    graph[q+c].append(q)
    graph[p+c].append(q+c)
    graph[q+c].append(p+c)

INF = 10 ** 9
dist = defaultdict(lambda: INF)

start = 1 << L
goal = N << L

q = [start] # 0 が会社に属していない状態
dist[start] = 0
d = 0
while q:
    qq = []
    while q:
        x = q.pop()
        if x & mask == 0:
            for y in graph[x]:
                if dist[y] <= d + 1:
                    continue
                dist[y] = d + 1
                qq.append(y)
        else:
            for y in graph[x]:
                if dist[y] <= d:
                    continue
                dist[y] = d
                q.append(y)
    d += 1
    q = qq

answer = dist[goal]
if answer == INF:
    answer = -1
print(answer)
### BUGGY CODE ###

mod=10**9+7
k=int(input())
s=input()
n=len(s)
c=1
t=1
ans=0
m=10**20
for i in range(k+1):
  ans+=c*t
  if ans>m:ans%=mod
  c*=(n+k-i)*pow(i+1,mod-2,mod)
  if c>m:c%=mod
  t*=25
  if t>m:t%=mod
print(ans%mod)


### FIXED CODE ###

mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
k=int(input())
s=input()
n=len(s)
ans=0
for i in range(k,-1,-1):
  ans+=comb(n+k,i)*pow(25,i,mod)
  ans%=mod
print(ans%mod)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
max_a=max(A)
dp=[True]*(max_a+1)
ans=0
for i in range(N):
  a=A.pop()
  #print(a)
  if dp[a]==False:
    continue
  if a not in A:
    ans+=1
  i=1
  k=a
  while k<=max_a:
    dp[k]=False
    i+=1
    k=a*i
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
max_a=A[-1]
dp=[True]*(max_a+1)
ans=0
for i in range(N):
  a=A[i]
  #print(a)
  if dp[a]==True: 
    if i==N-1:
      ans+=1
    elif a!=A[i+1]:
      ans+=1
    
    k=a
    while k<=max_a:
      dp[k]=False    
      k+=a
print(ans)
### BUGGY CODE ###

S = input()
mod = 10 ** 9 + 7

dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1
cnt = 1

for i, s in enumerate(S[::-1]):
    if s == "?":
        for x in range(13):
            for y in range(10):
                next_x = y * 10 ** i + x
                dp[i+1][next_x % 13] += dp[i][x]
                dp[i+1][next_x % 13] %= mod
    else:
        for x in range(13):
            next_x = int(s)*10**i+x
            dp[i + 1][next_x % 13] = dp[i][x]


ans = dp[-1][5] % mod
print(ans)


### FIXED CODE ###

S = input()
mod = 10 ** 9 + 7

dp = [0]*13
dp[0] = 1

mul = 1
for i, s in enumerate(S[::-1]):
    new = [0]*13
    if s == "?":
        for x in range(13):
            for y in range(10):
                next_x = y * mul + x
                new[next_x % 13] += dp[x]
                new[next_x % 13] %= mod
    else:
        for x in range(13):
            next_x = int(s) * mul + x
            new[next_x % 13] = dp[x]

    dp = new
    mul *= 10
    mul %= 13

ans = dp[5] % mod
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
INF = float('inf')
weight = [0] * N
value = [0] * N
Max_v = 0
for i in range(N):
    w, v = map(int, input().split())
    weight[i], value[i] = w, v
    Max_v += v

dp = [[INF]*(Max_v+1) for _ in range(N)]
for i in range(0, value[0]+1):
    dp[0][i] = weight[0] if i else 0

for i in range(1, N):
    for vs in range(Max_v+1):
        if vs - value[i] >= 0:
            dp[i][vs] = dp[i-1][vs - value[i]] + weight[i]
        else:
            dp[i][vs] = weight[i]
        dp[i][vs] = min(dp[i][vs], dp[i-1][vs])

for i in reversed(range(Max_v+1)):
    if dp[N-1][i] <= W:
        print(i)
        break


### FIXED CODE ###

N, W = map(int, input().split())
INF = float('inf')
weight = [0] * N
value = [0] * N
Max_v = 0
for i in range(N):
    w, v = map(int, input().split())
    weight[i], value[i] = w, v
    Max_v += v

dp = [[INF]*(Max_v+1) for _ in range(N)]
for i in range(0, value[0]+1):
    dp[0][i] = weight[0] if i else 0

for i in range(1, N):
    for vs in range(Max_v+1):
        if vs - value[i] >= 0:
            dp[i][vs] = dp[i-1][vs - value[i]] + weight[i]
        else:
            dp[i][vs] = weight[i]
        dp[i][vs] = min(dp[i][vs], dp[i-1][vs])

for i in reversed(range(Max_v+1)):
    if dp[N-1][i] <= W:
        print(i)
        break
### BUGGY CODE ###

# ABC77 C - Snuke Festival
from bisect import bisect_left
from bisect import bisect_right
import numpy as np

N = int(input())
A = np.array(sorted(list(map(int, input().split()))))
B = np.array(sorted(list(map(int, input().split()))))
C = np.array(sorted(list(map(int, input().split()))))

ans = 0
for i in range(N):
#    ans += bisect_left(A, B[i]) * (N - bisect_right(C, B[i]))
    ans += np.count_nonzero(A < B[i]) * np.count_nonzero(C > B[i])
print(ans)

### FIXED CODE ###

# ABC77 C - Snuke Festival
from bisect import bisect_left
from bisect import bisect_right
from bisect import bisect

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

ans = 0
for i in range(N):
    ans += bisect_left(A, B[i]) * (N - bisect_right(C, B[i]))

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

alph = 'abcdefghijklmnopqrstuvwxyz'
n = int(input())
cou = 0
name = ['']
key = True

while key:
  tmp = name.pop(0)
  for s in alph:
    name.append(tmp + s)
    cou += 1
    if cou==n:
      key = False
      break
print(tmp+s)

### FIXED CODE ###

# けんちょんさんの記事見た！
# https://drken1215.hatenablog.com/entry/2020/06/21/225500
N = int(input())
res = ''

while N:
  N -= 1
  res += chr(ord('a') + N%26)
  N //= 26

print(res[::-1])  # 🍡( ´ ꒳ `🌸)さんありがとー٩(๑❛0❛๑)۶
### BUGGY CODE ###

from collections import deque

MOD = 10**9+7
n, k = map(int,input().split())
e = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
    
color = [-1]*n
d = deque()
d.append(0)
while d:
    f = d.pop()
    tmp = deque()
    tmp.append([f, 0])
    p = deque()
    while tmp:
        cf, cd = tmp.pop()
        if cd >= 2:
          break
        for i in e[cf]:
            if i == f:
                continue
            tmp.appendleft([i, cd+1])
            if not i in p:
                p.append(i)
    cnt = 0
    while p:
        cf = p.pop()
        if color[cf] != -1:
            cnt += 1
    color[f] = k - cnt
    for i in e[f]:
        if color[i] == -1:
            d.appendleft(i)
            
ans = 1
for i in range(n):
    ans = ans * color[i] % MOD
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Aug 25 08:44:21 2020

@author: teppe
"""

from collections import deque

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs

MOD = 10**9+7
fact, fact_inv = prepare(10+10**5, MOD)

def perm(n,k):
  if k > n or k < 0:
    return 0
  return fact[n] * fact_inv[n-k] % MOD


n, k = map(int,input().split())
e = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
 
colored = [False]*n
colored[0] = True
num = len(e[0])
ans = perm(k, 1+num)
d = deque()
for i in e[0]:
    colored[i] = True
    d.append(i)
while d:
    f = d.pop()
    num = len(e[f]) - 1
    if num == 0:
        continue
    ans *= perm(k-2, num)
    ans %= MOD
    for i in e[f]:
        if not colored[i]:
            colored[i] = True
            d.appendleft(i)
print(ans % MOD)
### BUGGY CODE ###

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

X=list(map(int,input().split()))

X.append(x)

X.sort()

dif=[]
for i in range(n):
    dif.append(X[i+1]-X[i])

for j in range(max(dif),0,-1):
    if all(x%j==0  for x  in dif):
        print(j)
        break

### FIXED CODE ###

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

X=list(map(int,input().split()))

dif=[]
for i in range(n):
    dif.append(abs(X[i]-x))

def gcd(a,b):
    a,b=max(a,b),min(a,b)
    if b>0:
        return gcd(b,a%b)
    else:
        return a

ans=dif[0]
for i in range(1,n):
    ans=gcd(ans,dif[i])

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

n = int(input())
a = list(map(int, input().split()))
b = []

for i in range(n):
    if i%2 == 0:
        b.insert(0, str(a[i]))
    else:
        b.append(str(a[i]))

if n%2 == 0:
    ans = b[::-1]
else:
    ans = b

ans = ' '.join(ans)
print(ans)

### FIXED CODE ###

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


if n%2 == 0:
    for i in range(n-1,-1,-2):
        print(a[i], end=' ')
    for i in range(0, n, 2):
        print(a[i], end=' ')
    
elif n%2 == 1:
    for i in range(n-1,-1,-2):
        print(a[i], end=' ')
    for i in range(1, n, 2):
        print(a[i], end=' ')
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = set(a)
ans = 0
for i in b:
  tmp = a.count(i)
  if tmp!=i:
    if tmp<i:
      ans+=tmp
    else:
      ans+=tmp-i
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
counter = Counter(a)
ckey = list(counter.keys())
cval = list(counter.values())
ans = 0

for i in range(len(ckey)):
  if ckey[i]>cval[i]:
    ans+=cval[i]
  elif ckey[i]<cval[i]:
    ans+=cval[i]-ckey[i]
print(ans)
### BUGGY CODE ###

n = int(input())
v = list(map(int, input().split()))
i_num = 0
two_0 = []
two_1 = []
t1 = 10 ** 5
ans = 0
for i in v:
    if i_num % 2 == 0:
        two_0.append(i)
    else:
        two_1.append(i)
    i_num += 1
c = 0
for i in two_0:
    if c < two_0.count(i):
        c = two_0.count(i)
        t0 = i
for i in two_0:
    if i != t0:
        ans += 1
c = 0
for i in two_1:
    if c < two_1.count(i) and i != t0:
        c = two_1.count(i)
        t1 = i
for i in two_1:
    if i != t1:
        ans += 1
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
v = list(map(int, input().split()))
gu, ki = [], []
for i in range(n):
	if i % 2 == 0:
		ki.append(v[i])
	else:
		gu.append(v[i])
ki_flag, gu_flag = False, False
kict = Counter(ki)
guct = Counter(gu)
kict_mc = kict.most_common()
guct_mc = guct.most_common()
if len(kict_mc) > 1:
	ki_flag = True
if len(guct_mc) > 1:
	gu_flag = True
ki_first = kict_mc[0][0]
if ki_flag:
	ki_second = kict_mc[1][0]
gu_first = guct_mc[0][0]
if gu_flag:
	gu_second = guct_mc[1][0]
if ki_flag & gu_flag:
	if ki_first == gu_first:
		print(min([n - kict_mc[0][1] - guct_mc[1][1], n - kict_mc[1][1] - guct_mc[0][1]]))
	else:
		print(n - kict_mc[0][1] - guct_mc[0][1])
elif ki_flag:
	if ki_first == gu_first:
		print(n - kict_mc[1][1] - guct_mc[0][1])
	else:
		print(n - kict_mc[0][1] - guct_mc[0][1])
elif gu_flag:
	if ki_first == gu_first:
		print(n - kict_mc[0][1] - guct_mc[1][1])
	else:
		print(n - kict_mc[0][1] - guct_mc[0][1])
else:
	if ki_first == gu_first:
		print(int(n / 2))
	else:
		print(n - kict_mc[0][1] - guct_mc[0][1])
### BUGGY CODE ###

N = int(input())
A = [int(_) for _ in input().split()]
cumsum = [0]
for a in A:
    cumsum += [cumsum[-1] + a]
ans = 0
for i in range(N):
    for j in range(i + 1, N + 1):
        ans += cumsum[j] - cumsum[i] == 0
print(ans)


### FIXED CODE ###

import heapq
N = int(input())
A = [int(_) for _ in input().split()]
cumsum = [0]
for a in A:
    cumsum += [cumsum[-1] + a]
heapq.heapify(cumsum)
before = 10 ** 10
count = 0
ans = 0
while cumsum:
    now = heapq.heappop(cumsum)
    count += before == now
    if not (before == now and cumsum):
        ans += count * (count + 1) // 2
        count = 0
    before = now
print(ans)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    s = sum(a)
    t = 1
    m = 2**(s//2+1)
    for c in a:
        t |= t << c
    t %= m

    return s - (t.bit_length() - 1)


print(main())




### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    s = sum(a)
    t = 1
    m = 2**(s//2+1) - 1
    for c in a:
        t |= t << c
    t &= m

    return s - (t.bit_length() - 1)


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

N=int(input())
L=list(map(int,input().split()))
for i in range(1,N+1):
  print(L.index(i)+1,end="")
  if i<N:
    print(" ",end="")
print()

### FIXED CODE ###

N=int(input())
L=[0]*N
for x,i in enumerate(list(map(int,input().split()))):
  L[i-1]=str(x+1)
print(' '.join(L))
### BUGGY CODE ###

#coding:utf-8
N,M  = map(int,input().split())
A = list(map(int,input().split()))
b = 0
c = [0,2,5,5,4,5,6,3,7,6]
bagS = [[] for i in range(N+1)]
def check(A,B):#A:prev,B:temp
    As = list(map(str,sorted(A,reverse=True)))
    p = int("".join(As)) if len(A) else 0

    B.sort(reverse=True)
    Bs = list(map(str,B))
    
    t = int("".join(Bs)) if len(B) else 0
    if t > p:
        return B
    else :
        return A
def check2(A,B):
    p = 0
    t = 0
    for a in A:
        p = p*10+a
    for b in B:
        t = t*10+b
    if t > p:
        return B

    else:
        return A

while b != N:

    for a in A:
        if b+ c[a] <= N:
  
            bagS[b+c[a]] = check2(bagS[b+c[a]],bagS[b]+[a])

    for i in range(b+1,N+1):
        if bagS[i]:
            b = i
            break
print("".join(list(map(str,bagS[N]))))



### FIXED CODE ###

#coding:utf-8
N,M  = map(int,input().split())
A = list(map(int,input().split()))
b = 0
c = [0,2,5,5,4,5,6,3,7,6]
bagS = [[] for i in range(N+1)]

def check2(A,B):
    p = 0
    t = 0
    # print(A)
    # print(B)
    if len(A) > len(B):
        return A
    elif len(A) < len(B):
        return B
    for a,b in zip(A,B):
        if  a- b > 0:
            return A
        elif a-b < 0:
            return B
    return A
    # for a in A:
    #     p = p*10+a
    # for b in B:
    #     t = t*10+b
    # if t > p:
    #     return B

    # else:
    #     return A

while b != N:

    for a in A:
        if b+ c[a] <= N:
  
            bagS[b+c[a]] = check2(bagS[b+c[a]],sorted((bagS[b]+[a]),reverse=True))

    for i in range(b+1,N+1):
        if bagS[i]:
            b = i
            break
print("".join(list(map(str,bagS[N]))))