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

n=int(input())
arr=input().split(" ")
arr_s=set(arr)

#print(arr)
a=0
most_e=0
most_o=0
arr_e=[0 for i in range(int(n/2))]
arr_o=[0 for i in range(int(n/2))]
for i in range(int(n/2)):
    arr_e[i]=arr[a]
    arr_o[i]=arr[a+1]
    a+=2
#print(arr_e,arr_o)
arr_es=set(arr_e)
arr_os=set(arr_o)
#print(arr_es,arr_os)

for i in arr_es:
    cnt_e=arr_e.count(i)
    if cnt_e>most_e:
        most_e=cnt_e
        
for i in arr_os:
    cnt_o=arr_o.count(i)
    if cnt_o>most_o:
        most_o=cnt_o

#print(most_e,most_o)
if len(arr_s)==1:
    print(int(n/2))
else:
    print(n-most_e-most_o)

### FIXED CODE ###

import collections
n=int(input())
arr=input().split(" ")
arr_s=set(arr)
a=0
arr_e=[0 for i in range(int(n/2))]
arr_o=[0 for i in range(int(n/2))]
for i in range(int(n/2)):
    arr_e[i]=arr[a]
    arr_o[i]=arr[a+1]
    a+=2
ce=collections.Counter(arr_e).most_common()
co=collections.Counter(arr_o).most_common()
if len(arr_s)==1:
    print(int(n/2))
else:
    if ce[0][0]!=co[0][0]:
        print(n-ce[0][1]-co[0][1])
    else:
        print(n-max(ce[0][1]+co[1][1],ce[1][1]+co[0][1]))
### BUGGY CODE ###

# coding:utf-8

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

for i in range(n - 1):
    cum = sum(a[i + 1:])
    ans += a[i] * cum

print(ans % (10**9 + 7))


### FIXED CODE ###

# coding:utf-8
import itertools
n = int(input())
a = list(map(int, input().split()))
cum = [0] + list(itertools.accumulate(a))
# print(cum)
ans = 0
mod = 10**9 + 7

for i in range(n):
    ans += a[i] * cum[i]
    # print(a[i], cum[i])

print(ans % mod)
### BUGGY CODE ###

S = list(input())
count = 0

for i in range(len(S)):
  if S[i] == 'W':
    for j in range(i):
      if S[j] == 'B':
        S[i] = 'B'
        S[j] = 'W'
        count += (i-j)
        break
print(count)

### FIXED CODE ###

S = list(input())
count = 0
valueA = 0
for i in range(len(S)):
  if S[i] == 'B':
    count += 1
    valueA += i

valueB = 0
for i in range(count):
  valueB += (len(S) - 1 - i)
  
print(valueB - valueA)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)

### FIXED CODE ###

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

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)] #全方向調べる

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)
### BUGGY CODE ###

n=int(input())
lisa=[]
for i in range(n):
    a=input()
    lisa.append(a)
ans=0
add=[]
for i in range(n):
    if ans<lisa.count(lisa[i]):
        ans=lisa.count(lisa[i])
for i in range(n):
    if lisa.count(lisa[i])==ans:
        add.append(lisa[i])
add=sorted(list(set(add)))
for i in range(len(add)):
    print(add[i])

### FIXED CODE ###

n=int(input())
S=[]
ans=0
import collections
for i in range(n):
    s=input()
    S.append(s)
S=sorted(S)
c=collections.Counter(S)
ANS=[]
for i in range(n-1):
    if (S[i]!=S[i+1] and ans<c[S[i]]) or i==n-2:
        ans=c[S[i]]#Sの？番目がSにいくつあるのか
        ANS.append(ans)
inko=""
ans=max(ANS)
for i in range(n):
    if c[S[i]]==ans and S[i]!=inko:
        print(S[i])
        inko=S[i]
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
import heapq

def main():
    N,M = map(int,input().split())
    q = list(map(int, input().split()))
    total = sum(q)
    q.sort()

    for i in range(M):
        B, C = map(int,input().split())
        for j in range(B):
            tmp = q.pop(0)

            if tmp < C:
                q.insert(0,C)
                total += (C - tmp)
                q.sort()
            else:
                q.insert(0,tmp)
                break

    print(total)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
import heapq

def main():
    N,M = map(int,input().split())
    q = list(map(int, input().split()))
    X = [list(map(int,input().split())) for _ in range(M)]
    X.sort(key=lambda x:-x[1])
    total = sum(q)
    heapq.heapify(q)

    for i in range(M):
        for j in range(X[i][0]):
            tmp = heapq.heappushpop(q, X[i][1])
            if tmp < X[i][1]:
                total += (X[i][1] - tmp)
            else:
                break

    print(total)

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

import sys
sys.setrecursionlimit(10**8)
class SegTee:
    
    def __init__(self):
        self.arr=[0]*(4*n)
    def update(self,node,start,end,index,val):
        if index <start or index>end:
            return
        
        if start==end:
            #print(node,val)
            
            self.arr[node]=val
        else:
            mid=(start+end)//2
            self.update(2*node+1,start,mid,index,val)
            self.update(2*node+2,mid+1,end,index,val)
            self.arr[node]=max(self.arr[2*node+1],self.arr[2*node+2])
            
    def query(self,node,tl,tr,l,r):
        if tl>r or tr<l:
            return 0
        elif tl>=l and tr<=r:
            return self.arr[node]
        else:    
            mid=(tr+tl)//2
            p1=self.query(2*node+1,tl,mid,l,r)
            p2=self.query(2*node+2,mid+1,tr,l,r)
            return max(p1,p2)
    
n=int(input())
hi=[int(k) for k in input().split()]
co=[int(k) for k in input().split()]
#print(hi)
#print(co)
segTree=SegTee()
dp=[0]*(n)
ans=0
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  dp[i]=y+co[i]
  ans=max(ans,dp[i])
  #print(dp[i])
  segTree.update(0,0,n-1,x-1,dp[i])
  #print(segTree.arr)
#print(dp)
print(ans)  
      

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
class SegTee:
    
    def __init__(self):
        self.arr=[0]*(4*n)
    def update(self,node,start,end,index,val):
        if index <start or index>end:
            return
        
        if start==end:
            #print(node,val)
            
            self.arr[node]=val
        else:
            mid=(start+end)//2
            self.update(2*node+1,start,mid,index,val)
            self.update(2*node+2,mid+1,end,index,val)
            self.arr[node]=max(self.arr[2*node+1],self.arr[2*node+2])
            
    def query(self,node,tl,tr,l,r):
        if tl>r or tr<l:
            return 0
        elif tl>=l and tr<=r:
            return self.arr[node]
        else:    
            mid=(tr+tl)//2
            p1=self.query(2*node+1,tl,mid,l,r)
            p2=self.query(2*node+2,mid+1,tr,l,r)
            return max(p1,p2)
    

n = int(raw_input())
hi = list(map(int,raw_input().split()))
co= list(map(int,raw_input().split()))
#print(hi)
#print(co)
segTree=SegTee()
dp=[0]*(n)
ans=0
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  dp[i]=y+co[i]
  ans=max(ans,dp[i])
  #print(dp[i])
  segTree.update(0,0,n-1,x-1,dp[i])
  #print(segTree.arr)
#print(dp)
print(segTree.query(0,0,n-1,0,n-1))
### BUGGY CODE ###

N = int(input())

P=1
for i in range(1,N+1):
   P=P*i

print(P%1000000007)


### FIXED CODE ###

N = int(input())
M = 1000000007
n=[1]*(N+1)
for i in range(1,N+1):
    n[i] = (n[i-1]*i)%M

print(n[N])
### BUGGY CODE ###

L,R = map(int,input().split())

if L-R > 672:
    print(0)
else:
    minMod = 100000000
    for i in range(L,R):
        for j in range(i+1,R+1):
            tmp = (i*j)%2019
            if tmp == 0:
                minMod = 0
                break
            elif minMod > tmp:
                minMod = tmp
    print(minMod)

### FIXED CODE ###

L,R = map(int,input().split())

if R-L > 672:
    print(0)
else:
    minMod = 2019
    for i in range(L,R):
        for j in range(i+1,R+1):
            tmp = (i*j)%2019
            if tmp == 0:
                minMod = 0
                break
            minMod = min(tmp,minMod)
    print(minMod)
### BUGGY CODE ###

def _print_sum(cache):
    sum_value = 0
    for v, indices in cache.items():
        sum_value += v * len(indices)
    print(sum_value)


def _main(N, A_list, Q, BC_list):
    cache = {}
    values = set()
    for i, a in enumerate(A_list):
        cache.setdefault(a, []).append(i)
        values.add(a)

    for b, c in BC_list:
        indices = cache.get(b, [])
        cache[b] = []
        cache.setdefault(c, []).extend(indices)
        _print_sum(cache)


def _entry():
    N = int(input())
    A_list = list(map(int, input().split()))
    Q = int(input())
    BC_list = []
    for i in range(Q):
        B, C = map(int, input().split())
        BC_list.append((B, C))
    _main(N, A_list, Q, BC_list)


if __name__ == "__main__":
    _entry()


### FIXED CODE ###

def _calc_sum(cache):
    sum_value = 0
    for v, indices in cache.items():
        sum_value += v * len(indices)
    return sum_value


def _main(N, A_list, Q, BC_list):
    cache = {}
    for i, a in enumerate(A_list):
        cache.setdefault(a, []).append(i)

    sum_value = _calc_sum(cache)

    for b, c in BC_list:
        indices = cache.get(b, [])
        cache[b] = []
        sum_value -= b * len(indices)
        cache.setdefault(c, []).extend(indices)
        sum_value += c * len(indices)
        print(sum_value)


def _entry():
    N = int(input())
    A_list = list(map(int, input().split()))
    Q = int(input())
    BC_list = []
    for i in range(Q):
        B, C = map(int, input().split())
        BC_list.append((B, C))
    _main(N, A_list, Q, BC_list)


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

def solve():
    N = int(input())
    S = list(input())
    Q = int(input())
    set_dic = {}

    for i, s in enumerate(S):
        if s not in set_dic.keys():
            set_dic[s] = {i+1}
        else:
            set_dic[s].add(i+1)

    anslist = []

    for _ in range(Q):
        query1, query2, query3 = input().split()
        if query1 == "1":
            i = int(query2)
            c = query3
            cap = S[i-1]
            if cap == c:
                continue
            set_dic[cap].discard(i)
            if c not in set_dic.keys():
                set_dic[c] = {i}
            else:
                set_dic[c].add(i)
            S[i-1] = c
        else:
            l = int(query2)
            r = int(query3)
            ansset = set()
            ans = 0
            for eachset in set_dic.values():
                for i in range(l, r + 1):
                    if i in eachset:
                        ans += 1
                        break
            anslist.append(ans)

    for i in anslist:
        print(i)

if __name__ == '__main__':
    solve()

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    S = list(input())
    Q = int(input())
    set_dic = {}

    for i, s in enumerate(S):
        if s not in set_dic:
            set_dic[s] = [i+1]
        else:
            bisect.insort_left(set_dic[s], i+1)

    anslist = []

    for _ in range(Q):
        query1, query2, query3 = input().split()
        if query1 == "1":
            i = int(query2)
            c = query3
            cap = S[i-1]
            if cap == c:
                continue
            set_dic[cap].remove(i)
            if c not in set_dic:
                set_dic[c] = [i]
            else:
                bisect.insort_left(set_dic[c], i)
            S[i-1] = c
        else:
            l = int(query2)
            r = int(query3)
            ansset = set()
            ans = 0
            for eachlist in set_dic.values():
                li = bisect.bisect_left(eachlist, l)
                ri = bisect.bisect_right(eachlist, r)
                if li != ri:
                    ans += 1
            anslist.append(ans)

    for i in anslist:
        print(i)

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

a, b, n = map(int, input().split(" "))

max_score = 0
y = b // a

for x in range(max(y - 10000000, 1) , min(y + 20000000, n+1)):
    score = a * x // b - a * ( x // b )
    if score > max_score:
        max_score = score
print(max_score)


### FIXED CODE ###

a, b, n = map(int, input().split(" "))

max_score = 0
y = min(b, n)

for x in range(max(y - 100000, 1) , min(y + 200000, n+1)):
    score = a * x // b - a * ( x // b )
    if score > max_score:
        max_score = score
print(max_score)
### 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()))

AB = []
ABC = []

for i in A:
    for j in B:
        AB.append(i+j)

AB.sort(reverse=True)
AB_max = AB[:K]

for j in AB_max:
    for h in C:
        ABC.append(j+h)

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])

### FIXED 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()))

AB = []
ABC = []

for i in A:
    for j in B:
        AB.append(i+j)

AB.sort(reverse=True)
AB_max = AB[:K]

for j in AB_max:
    for h in C:
        ABC.append(j+h)

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

def resolve():

    s=str(input())
    K=int(input())

    ls=[]
    for i in range(len(s)):
        for j in range(i+1,len(s)+1):
            ls.append(s[i:j])

    print(sorted(set(ls))[K-1])


resolve()

### FIXED CODE ###

def resolve():

    s=str(input())
    K=int(input())

    ls=[]
    for i in range(len(s)):
        for j in range(i+1,i+K+1):
            ls.append(s[i:j])

    print(sorted(set(ls))[K-1])


resolve()
### BUGGY CODE ###

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

def grid(y,x):
    global dp
    if mp[y][x]!='#' and dp[y][x]==0:
        for dx,dy in [(-1,0),(0,-1)]:
            nx,ny=x+dx,y+dy
            dp[y][x]+=grid(ny,nx)
    return dp[y][x]


H,W=map(int,input().split())
mp=[['#']*(W+2)]
for _ in range(H):
    mp.append(['#']+list(input())+['#'])
mp.append(['#']*(W+2))

dp=[[0]*(W+2)for _ in range(H+2)]
dp[1][1]=1
grid(H,W)
print(dp[H][W]%(10**9+7))


### FIXED CODE ###

import sys
input=sys.stdin.readline

def grid(y,x,mp):
    mod=10**9+7
    dp=[[0]*x for _ in range(y)]
    dp[0][0]=1
    for h in range(y):
        for w in range(x):
            if mp[h][w]=='.':
                if 1<=h<y and 1<=w<x:
                    dp[h][w]=((dp[h][w-1]+dp[h-1][w])%mod)
                elif h==0 and 1<=w<x:
                    dp[h][w]=(dp[h][w-1]%mod)
                elif 1<=h<y and w==0:
                    dp[h][w]=(dp[h-1][w]%mod)
    return dp[y-1][x-1]


H,W=map(int,input().split())
mp=[list(input()) for _ in range(H)]
print(grid(H,W,mp))
### BUGGY CODE ###

N = int(input())
a = [int(i) for i in input().split()]
sum_a = sum(a)
b = []
for i in range(N-1):
    b.append(abs(2*sum(a[:i+1])-sum_a))
print(min(b))


### FIXED CODE ###

N = int(input())
a = [int(i) for i in input().split()]
sum_a = sum(a)
b = []
c = 0
for i in range(N-1):
    c += a[i]
    b.append(abs(2*c-sum_a))
print(min(b))
### BUGGY CODE ###

n = int(input())
x = '0b' + input()

for i in range(n):
    lisx = list(x)
    lisx[i+2] = str(1 - int(lisx[i+2]))
    xx = ''.join(lisx)
    intx = int(xx, 2)
    len1 = xx.count('1')

    cnt = 0
    while True:
        if intx == 0:
            print(cnt)
            break
        
        intx = intx % len1
        xx = bin(intx)
        len1 = xx.count('1')
        cnt += 1

### FIXED CODE ###

n = int(input())
s = input()
x = [int(i) for i in s]
pc = s.count('1')

def popcnt(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

def f(x):
    if x == 0:
        return 0
    return f(x % popcnt(x)) + 1

ans = [0]*n
for a in range(2):
    npc = pc
    if a == 0:
        npc += 1
    else:
        npc -= 1
    
    if npc <= 0:
        continue
    
    r0 = 0
    for i in range(n):
        r0 = (r0*2) % npc
        r0 += x[i]

    k = 1
    for i in range(n-1, -1, -1):
        if x[i] == a:
            r = r0
            if a == 0:
                r = (r+k) % npc
            else:
                r = (r-k+npc) % npc
            ans[i] = f(r) + 1
        k = (k*2) % npc

for i in ans:
    print(i)
### BUGGY CODE ###

from collections import deque

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

A = [["" for _ in range(W)] for _ in range(H)]

stack = deque()
for i in range(H):
    tmp = list(input())
    for j in range(W):
        A[i][j] = tmp[j]
        if tmp[j] == "#":
            stack.append((i,j))

ans = 0
flag = False
if stack:
    flag = True
while flag:
    ans += 1
    #print(ans, stack)
    flag = False
    new_stack = deque()
    for a,b in stack:
        #a,b = stack.pop() # 取り出す
        # A[a][b]の隣接マスについて調べる
        if a != 0: # 上
            if A[a-1][b] == ".": # 白の場合
                A[a-1][b] = "#"
                new_stack.append((a-1,b))
        if a != H-1: # 下
            if A[a+1][b] == ".": # 白の場合
                A[a+1][b] = "#"
                new_stack.append((a+1,b))
        if b != 0: # 左
            if A[a][b-1] == ".": # 白の場合
                A[a][b-1] = "#"
                new_stack.append((a,b-1))
        if b != W-1: # 右
            if A[a][b+1] == ".": # 白の場合
                A[a][b+1] = "#"
                new_stack.append((a,b+1))
    stack = new_stack
    if stack:
        flag = True
    else:
        ans -= 1 

print(ans)
        






### FIXED CODE ###

from collections import deque

def main():
    H,W = map(int, input().split())

    A = [[a for a in input()] for _ in range(H)]
    #stack = deque([(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"])
    stack = [(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"]
    ans = 0
    flag = False
    if stack:
        flag = True
    while flag:
        ans += 1
        flag = False
        #new_stack = deque()
        new_stack = []
        for a,b in stack:
        #while stack:
            #a,b = stack.pop() # 取り出す
            # A[a][b]の隣接マスについて調べる
             # 上
            if a != 0 and A[a-1][b] == ".": # 白の場合
                    A[a-1][b] = "#"
                    new_stack.append((a-1,b))
             # 下
            if a != H-1 and A[a+1][b] == ".": # 白の場合
                    A[a+1][b] = "#"
                    new_stack.append((a+1,b))
            # 左
            if b != 0 and A[a][b-1] == ".": # 白の場合
                    A[a][b-1] = "#"
                    new_stack.append((a,b-1))
            # 右
            if b != W-1 and A[a][b+1] == ".": # 白の場合
                    A[a][b+1] = "#"
                    new_stack.append((a,b+1))
        stack = new_stack
        if stack:
            flag = True
        else:
            ans -= 1 

    print(ans)
            


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

N = int(input())
C = []
S = []
F = []
for i in range(N-1):
    c, s, f = map(int, input().split())
    C.append(c)
    S.append(s)
    F.append(f)


for i in range(N - 1):
    time = S[i] + C[i]
    for j in range(i+1, N-1):
        cnt = 0
        while time > S[j] + F[j] * cnt:
            cnt += 1

        time = S[j] + F[j] * cnt + C[j]
    
    print(time)

print(0)

### FIXED CODE ###

N = int(input())

C = []; S = []; F = []
for i in range(N-1):
    c, s, f = map(int, input().split())
    C.append(c); S.append(s); F.append(f)

for i in range(N):
    t = 0
    for j in range(i, N-1):
        if t <= S[j]:
            t = S[j]
        elif t % F[j] == 0:
            pass
        elif t % F[j] !=0:
            t += F[j] - (t%F[j])
        t += C[j]
    print(t)
### BUGGY CODE ###

from collections import Counter
from fractions import gcd
n = int(input())
mod = 10**9+7
A = list(map(int,input().split()))
ans1 = 1
for i in range(n):
  ans1 *= A[i] // gcd(A[i], ans1)
ans = 0
for i in range(n):
  if A[i] > 0:
    ans += ans1 // A[i]
    ans %= mod
print(ans)

### FIXED CODE ###

from fractions import gcd
def lcm(x,y):
  return (x*y) // gcd(x,y)
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
l = a[0]
for i in range(1,n):
  l = lcm(l,a[i])
ans = 0
for i in range(n):
  ans += l//a[i]
print(ans%mod)
### BUGGY CODE ###

import math
n = int(input())
a = list(map(int, input().split()))
ans=0
x=[sum(a[:i]) for i in range(1,n+1)]
for i in set(x):
    t = x.count(i)
    if i != 0:
        if t >= 2:
            ans += math.factorial(t-1)
    else:
        ans += math.factorial(t)
print(ans)

### FIXED CODE ###

def com(x,y):
    a=1
    b=1
    y=min(y,x-y)
    for i in range(x,x-y,-1):
        a*=i
    for i in range(1,y+1):
        b*=i
    return a//b

n=int(input())
a=list(map(int,input().split()))
b=[a[0]]
for i in range(1,n):
    b.append(b[-1]+a[i])
from collections import Counter
c=Counter(b)
d=list(c.items())
ans=0
for t in d:
    if t[0]==0:
        ans+=com(t[1]+1,2)
    elif t[1]>1:
        ans+=com(t[1],2)
print(ans)
### BUGGY CODE ###

def lcs(x, y):
    lx = len(x)
    ly = len(y)
    pcsl = [[0 for i in range(ly + 1)] for j in range(lx + 1)]
    for i in range(lx):
        for j in range(ly):
            if x[i] == y[j]:
                pcsl[i][j] = pcsl[i - 1][j - 1] + 1
            else:
                pcsl[i][j] = max(pcsl[i - 1][j], pcsl[i][j - 1])
    print(pcsl[i][j])


q = int(input())

for i in range(q):
    ax = input()
    ay = input()
    lcs(ax, ay)

### FIXED CODE ###

def lcs_len(x, y):
    indices = [0]
    for y_i in y:
        t_index = 0
        for i, index in enumerate(indices, 1):
            c_index = x.find(y_i, t_index) + 1
            if c_index:
                if i < len(indices):
                    t_index = indices[i]
                    indices[i] = min(c_index, t_index)
                else:
                    indices.append(c_index)
                    break
    print(len(indices) - 1)


q = int(input())

for i in range(q):
    ax = input()
    ay = input()
    lcs_len(ax, ay)