Harryxun/stf_run huggingface dataset:
N, M = list(map(int,input().split()))
A_li = list(map(int,input().split()))
CB_li = []

for i in range(M):
    BandC = list(map(int,input().split()))
    BandC.reverse()
    CB_li.append(BandC)

CB_li.sort()
CB_li.reverse()
overwrite_li = []
for CB in CB_li:
    li = [CB[0]]*CB[1]
    overwrite_li.extend(li)

A_li.sort()
A_li.reverse()
j=0
for i in range(N):
    if A_li[i] < overwrite_li[j]:
        A_li[i] = overwrite_li[j]
        j+=1

ans = sum(A_li)
    
print(str(int(ans)))



### FIXED CODE ###

N, M = map(int,input().split())
A_li = list(map(int,input().split()))
CB_li = []
for i in range(M):
    B,C = map(int,input().split())
    CB_li.append([C,B])

CB_li.sort()
CB_li.reverse()

counter = 0
for i in range(M):
    li = [CB_li[i][0]]*CB_li[i][1]
    A_li.extend(li)
    counter += CB_li[i][1]
    if counter > N:
        break

A_li.sort()
ans = sum(A_li[-N:])
    
print(str(ans))
X ,Y ,A ,B ,C = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))
p.sort(reverse = True)
q.sort(reverse = True)
r.sort(reverse = True)
p = p[:X]
q = q[:Y]
p.extend(q)
p.sort()
for i in range(C) :
    if p[i] < r[i]:
        p[i] = r[i]
    else:
        pass
print(sum(p))

### FIXED CODE ###

X ,Y ,A ,B ,C = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))
p.sort(reverse = True)
q.sort(reverse = True)
r.sort(reverse = True)
p = p[:X]
q = q[:Y]
p.extend(q)
p.sort()
if X+Y > C:
    for i in range(C) :
        if p[i] < r[i]:
            p[i] = r[i]
        else:
            pass
else:
    for i in range(X+Y) :
        if p[i] < r[i]:
            p[i] = r[i]
        else:
            pass
print(sum(p))
N,K = map(int,input().split())
S = input()

letters = list(S)
letters[K] = letters[K].lower()

new_S = ""

for letter in letters:
  new_S += letter
  
print(new_S)

### FIXED CODE ###

N,K = map(int,input().split())
S = input()

letters = list(S)
letters[K-1] = letters[K-1].lower()

new_S = ""

for letter in letters:
  new_S += letter
  
print(new_S)
h,w=map(int,input().split())
disp=['A','B','C','D','E','F','G','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
for i in range(h):
  arr=list(map(str,input.split()))
  for j in range(w):
    if arr[j]=='snuke':
      print(disp[j]+str(i))

### FIXED CODE ###

h,w=map(int,input().split())
disp=['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
for i in range(h):
  arr=list(map(str,input().split()))
  for j in range(w):
    if arr[j]=='snuke':
      print(disp[j]+str(i+1))
from numba import njit

@ngit
def main(N, A):
    num = 1
    ans = 1
    if A[N] == 0:
        return -1
    for i in range(N+1):
        num -= A[i]
        if i < N:
            num *= 2
            ans += num
        if num <= 0 and i < N:
            return -1
    eda=0
    for i in range(N+1):
        ans -= num
        eda+=A[N-i]
        num -= eda
        num = num//2
        if num <= 0:
            num += A[N-i]
            break
    return ans


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

print(main(N, A))


### FIXED CODE ###

def main(N, A):
    num = 1
    ans = 1
    for i in range(N+1):
        num -= A[i]
        if i < N:
            num *= 2
            ans += num
        if num == 0 and i < N:
            return -1
        if num < 0:
            return -1
    eda = 0
    for i in range(N+1):
        ans -= num
        eda += A[N-i]
        num -= eda
        num = num//2
        if num <= 0:
            break
    return ans


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

print(main(N, A))
n = int(input())
c = list(input())
c = c[::-1]
cou = 0
for i in range(len(c)/2):
    if c[i] == "R":
        cou += 1
print(cou)

### FIXED CODE ###

n = int(input())
c = list(input())
print(c[:c.count("R")].count("W"))
import re

S = input()

print(max(re.findall('[ATCG]+', S)))

### FIXED CODE ###

import re

S=input()

ans=0
for i in range(10):
  for j in range(i,10+1):
    str=S[i:j]
    if re.search(r'^[AGCT]+$' ,str):
      ans=max(ans,len(str))

print(ans)
n = sys.stdin.readline().rstrip()
hon = [2, 4, 5, 7, 9]
pon = [0, 1, 6, 8]
bon = [3]
if int(n[-1]) in hon:
    print('hon') 
elif int(n[-1]) in pon:
    print('pon')
elif int(n[-1]) in bon:
    print('bon')

### FIXED CODE ###

import sys

n = sys.stdin.readline().rstrip()
hon = [2, 4, 5, 7, 9]
pon = [0, 1, 6, 8]
bon = [3]
if int(n[-1]) in hon:
    print('hon') 
elif int(n[-1]) in pon:
    print('pon')
elif int(n[-1]) in bon:
    print('bon')
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

import math
a, b = map(int,input().split())

if math.gcd(a, b) == 1:
    print(1)
else:
    print(len(factorization(math.gcd(a, b))) + 1)

### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

import fractions
a, b = map(int,input().split())

if fractions.gcd(a, b) == 1:
    print(1)
else:
    print(len(factorization(fractions.gcd(a, b))) + 1)
X=int(input())
for i in range(65):
    a=i
    for j in range(65):
        b=j
        if(a**5-b**5==X):
            A=a
            B=b
        b=-j
        if(a**5-b**5==X):
            A=a
            B=b
print(A,B)


### FIXED CODE ###

X=int(input())
for i in range(121):
    a=i
    for j in range(121):
        b=j
        if(a**5-b**5==X):
            A=a
            B=b
        b=-j
        if(a**5-b**5==X):
            A=a
            B=b
print(A,B)
import time
import random
N = int(input())
s = str(input())
maxlen = N//2
start = time.time()
def solve(tgt):
    for i in range(N-tgt*2+1):
        if s[i:i+tgt] in s[i+tgt:]:
            return True
    return False

ng = maxlen + 1
ok = 0
if N>650:
    ok = 2
first = 1
while ng-ok > 1:
    end = time.time()
    if end-start > 1.5:
        if ok >= 50:
            assert()
        r = random.random.randint(ok,ng-1)
        print(r)
        exit()
    tgt = (ok+ng)//2
    if first == 1:
        tgt = 8
        first = 0
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)


### FIXED CODE ###

from collections import defaultdict as dd
N = int(input())
s = str(input())
maxlen = N//2

def solve(tgt):
    dic = dd(int)
    st = s[tgt:2*tgt]
    dic[st] += 1
    ls = [st]
    for char in s[2*tgt:]:
        st = st[1:]+char
        dic[st] += 1
        ls.append(st)
    st = s[:tgt]
    if dic[st] > 0:
        return True
    dic[ls[0]] -= 1
    for i,char in enumerate(s[tgt:N-tgt]):
        st = st[1:]+char
        if dic[st] > 0:
            return True
        dic[ls[i+1]] -= 1
    return False

ng = maxlen + 1
ok = 0
while ng-ok > 1:
    tgt = (ok+ng)//2
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)
S = input()
if S[2]==S[3] and S[4]==S[5]:\
    print(Yes)
else:
    print(No)

### FIXED CODE ###

if __name__=='__main__':
    S = input()
    if S[2]==S[3] and S[4]==S[5]:\
      print('Yes')
    else:
      print('No')
N, X = map(int, input().split())
Xs = list(map(int, input().split()))
from math import gcd

lis = []
for x in Xs:
    lis.append(abs(x-X))

G = 0
for l in lis:
    G = gcd(l, G)
print(G)

### FIXED CODE ###

N, X = map(int, input().split())
Xs = list(map(int, input().split()))
from fractions import gcd

lis = []
for x in Xs:
    lis.append(abs(x-X))

G = 0
for l in lis:
    G = gcd(l, G)
print(G)
import sys
sys.setrecursionlimit(4100000)

def find(Data, x):
    if Data[x] < 0:
        return x
    else:
        Data[x] = find(Data, x)
        return Data[x] 

def unite(Data, a, b):
    a, b = find(Data, a), find(Data, b)
    if a != b:
        if Data[a] > Data[b]:
            Data[a] = Data[a] + Data[b]
            Data[b] = a
        else:
            Data[b] = Data[b] + Data[a]
            Data[a] = b 

n, m = map(int, input().split())
UF = [-1 for i in range(n)]
for i in range(m):
    ai, bi = map(int, input().split())
    ai, bi = ai - 1, bi - 1
    unite(UF, ai, bi)

ans = 0
for i in range(n):
    if UF[i] < 0: ans += 1 
print(ans - 1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def find(Data, x):
    if Data[x] < 0:
        return x
    else:
        Data[x] = find(Data, Data[x])
        return Data[x] 

def unite(Data, a, b):
    a, b = find(Data, a), find(Data, b)
    if a == b:
        pass
    elif Data[a] < Data[b]:
        Data[a] = Data[a] + Data[b]
        Data[b] = a
    else:
        Data[b] = Data[b] + Data[a]
        Data[a] = b 

n, m = map(int, input().split())
UF = [-1 for i in range(n)]
for i in range(m):
    ai, bi = map(int, input().split())
    ai, bi = ai - 1, bi - 1
    unite(UF, ai, bi)

ans = 0
for i in range(n):
    if UF[i] < 0: ans += 1 
print(ans - 1)
from scipy.special import comb

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

a_s = []
flag = False

for i in range(M):
    a_m = int(input())
    a_s.append(a_m)
    if(i > 0 and a_m == a_s[i-1]+1):
        flag = True
        print(0)
        break


if not flag:
    way = 1
    now = 0
    for a in a_s:
        # print("a = " + str(a))

        step = a - 1 - now
        # print("now = " + str(now))
        # print("step = " + str(step))
        w = 0
        for i in range(step//2+1):
            # print(str(step-i) + " C " + str(i))
            # print (scm.comb(step-i, i))
            w += comb(step-i, i)
        if(w != 0):
            way = w * way
        now = a+1
        # print(w)

    step = N - now
    # print("way = " + str(way))
    w = 0
    for i in range(step//2+1):
        # print(str(step-i) + " C " + str(i))
        # print (scm.comb(step-i, i))

        w += comb(step-i, i)
    # print("w = " +str(w))
    if(w != 0):
        way = w * way

    print(int(way % 1000000007))


### FIXED CODE ###

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

flag = [ 0 for i in range(N+1)]
dp = [0 for i in range(N+1)]

for _ in range(M):
    a = int(input())
    flag[a] = 1


dp[0] = 1
if flag[1] == 1:
    dp[1] = 0
else:
    dp[1] = 1;

for i in range(2, N+1):
    if flag[i] == 1:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

print(dp[N])
print("".join(sorted([input() for i in range(int(input().split[0]))])))

### FIXED CODE ###

def solve():
    n, _ = input().split()
    print("".join(sorted([input() for i in range(int(n))])))


if __name__=="__main__":
    solve()
l = [2, 1]

def l(x):
  if len(l) > x:
    return l[x]
  else:
    return l(x-1) + l(x-2)
  
print(l(int(input())))


### FIXED CODE ###

lu = [2, 1]
x = int(input())
for i in range(2, x+1):
    lu.append(lu[i-1] + lu[i - 2])  
print(lu[x])
N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
    def find(self, i):
        parent = self.parents[i]
        if parent == i:
            return i
        else:
            return self.find(parent)
    def unite(self, i, j):
        parent_i = self.parents[i]
        parent_j = self.parents[j]
        if parent_i == parent_j:
            pass
        else:
            size = self.sizes[i] + self.sizes[j]
            self.sizes[i] = size
            self.sizes[j] = size
            self.parents[i] = parent_j 
 
 
def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.sizes[px] * uf.sizes[py]
            uf.unite(px, py)
        ans.append(p)
 
    for a in reversed(ans[:-1]):
        print(a)
 
 
main()


### FIXED CODE ###

N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
 
 
class UnionFind:
    def __init__(self,size):
        self.rank = [-1 for _ in range(size)]
        self.number = [1 for _ in range(size)]
 
    def find(self,x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x
 
    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]
 
 
def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.number[px] * uf.number[py]
            uf.union(px, py)
        ans.append(p)
 
    for a in reversed(ans[:-1]):
        print(a)
 
 
main()
a = int(input())
c = 1

while (c <= a):
c = c * 2

print(int(c/2))

### FIXED CODE ###

a = int(input())
c = 1

while (c <= a):
	c = c * 2

print(int(c/2))
N=int(input())
s=[0]*N
t=[0]*N
for i in range(N):
  s[i],t[i] = input().split()
  t[i]=int(t[i])
X=input()

j= s.index(X)
if X==s[-1]:
  ans=0
else:
  ans= t[j+1:]

print(sum(ans))

### FIXED CODE ###

N=int(input())
s=[0]*N
t=[0]*N
for i in range(N):
  s[i],t[i] = input().split()
  t[i]=int(t[i])
X=input()

j= s.index(X)
if X==s[-1]:
  ans=0
else:
  ans= sum(t[j+1:])

print(ans)
from collections import deque
from collections import defaultdict
n, m = map(int, input().split())
g = defaultdict(list)
s = set(list(range(1, n+1)))
ans = 0
for i in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
while s:
  	ans += 1
    root = s.pop()
    q = deque()
    q.append(root)
    done = set()
    done.add(root)
    while q:
        node = q.popleft()
        for adj in g[node]:
            if adj not in done:
                done.add(adj)
                q.append(adj)
                s.remove(adj)
print(ans - 1)


### FIXED CODE ###

from collections import deque
from collections import defaultdict

n, m = map(int, input().split())
g = defaultdict(list)
s = set(list(range(1, n+1)))
ans = 0

for i in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

while s:
    root = s.pop()
    q = deque()
    q.append(root)
    done = set()
    done.add(root)

    while q:
        node = q.popleft()

        for adj in g[node]:
            if adj not in done:
                done.add(adj)
                q.append(adj)
                s.remove(adj)
    ans += 1

print(ans - 1)
H=input()
A=input()
h = int(H)
a = int(A)
if mod(H,A) == 0:
    n = H // A
else:
    n = H // A +1
print(n)

### FIXED CODE ###

H,A =input().split()
h = int(H)
a = int(A)
if h % a == 0:
    n = h // a
else:
    n = h // a +1
print(n)
n=input()
maxn=0
maxccount=0

for i in range(n+1):
  count=0
  while n-i%2==0:
    n=n/2
    count+=1
  if maxcount < count:
    maxn=i
    maxcount=count

print(maxn)
    

### FIXED CODE ###

n=int(input())
i=1
while i*2<=n:
  i*=2
print(i)
import collections
x, n = map(int,input().split())
P = list(map(int, input().split()))

PX = list(map(lambda p: p-x,P))
CPX = collections.Counter(PX)
ans = 0

for i in range(max(max(P),x))
  if CPX[-i] == 0:
    ans = x -i
    break
  elif CPX[i] == 0:
    ans = x +i
    break

print(ans)

### FIXED CODE ###

import collections
x, n= map(int, input().split())
P = list(map(int, input().split()))
 
PX = list(map(lambda p: p-x,P))
CPX = collections.Counter(PX)
ans = 0

for i in range(100):
  if CPX[-i] == 0:
    ans = x -i
    break
  elif CPX[i] == 0:
    ans = x +i
    break

print(ans)
a=list(map(int, input()))
a.sort()
print(a[0],a[1],a[2])


### FIXED CODE ###

ns=list(map(int,input().split()))
ns.sort()
print(ns[0],ns[1],ns[2])
moto=input()
count=0
countlist=[]
for i in range(len(moto)):
  if moto[i]=="A":
    count=count+1
  elif moto[i]=="T":
    count=count+1
  elif moto[i]=="G":
    count=count+1
  elif moto[i]=="C":
    count=count+1
  else:
    countlist.append(count)
    count=0
kotae=max(countlist)
print(kotae)
    

### FIXED CODE ###

moto=input()
count=0
countlist=[0]
for i in range(len(moto)):
  if moto[i]=="A" or moto[i]=="T" or moto[i]=="G" or moto[i]=="C":
    count=count+1
  else:
    countlist.append(count)
    count=0
countlist.append(count)
kotae=max(countlist)
print(kotae)
from bisect import bisect_left

while True:
    d = int(input())
    if not d:
        break
    n = int(input())
    m = int(input())
    stores = {0, d}
    for i in range(2, n + 1):
        stores.add(int(input()))
    sorted_stores = sorted(stores)

    total_dist = 0
    while m:
        k = int(input())
        i = bisect_left(sorted_stores, k)
        l, r = sorted_stores[i - 1:i + 1]
        total_dist += min(k - l, r - k)
        m -= 1
    print(total_dist)

### FIXED CODE ###

from bisect import bisect_left

while True:
    d = int(input())
    if not d:
        break
    n = int(input())
    m = int(input())
    stores = {0, d}
    for i in range(2, n + 1):
        stores.add(int(input()))
    sorted_stores = sorted(stores)

    total_dist = 0
    while m:
        k = int(input())
        i = bisect_left(sorted_stores, k)
        if i:
            l, r = sorted_stores[i - 1:i + 1]
            total_dist += min(k - l, r - k)
        m -= 1
    print(total_dist)
from collections import defaultdict
from itertools import accumulate

buf = []
while True:
    n, m = int(input())
    if n == 0:
        break
    hs = [int(input()) for _ in range(n)]
    ws = [int(input()) for _ in range(m)]
    ha = accumulate(hs)
    wa = accumulate(ws)
    hd = defaultdict(int)
    wd = defaultdict(int)

    for i in range(n):
        for j in range(i + 1, n):
            hd[ha[j] - ha[i]] += 1
            wd[wa[j] - wa[i]] += 1
    ans = 0
    for h, cnt in hd.items():
        if h in wd:
            ans += cnt * wd[h]
    buf.append(ans)

print('\n'.join(map(str, buf)))

### FIXED CODE ###

from collections import defaultdict
from itertools import accumulate

buf = []
while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    hs = [int(input()) for _ in range(n)]
    ws = [int(input()) for _ in range(m)]
    ha = [0] + list(accumulate(hs))
    wa = [0] + list(accumulate(ws))
    hd = defaultdict(int)
    wd = defaultdict(int)

    for i in range(n + 1):
        for j in range(i + 1, n + 1):
            hd[ha[j] - ha[i]] += 1
    for i in range(m + 1):
        for j in range(i + 1, m + 1):
            wd[wa[j] - wa[i]] += 1
    ans = 0
    for h, cnt in hd.items():
        if h in wd:
            ans += cnt * wd[h]
    buf.append(ans)

print('\n'.join(map(str, buf)))
s = list(input())
n = len(s)

for i in range(n):
    if i == 0 and s[i] == "?":
        if s[i+1] == "D" or s[i+1] == "?":
            s[i] = "P"
        else:
            if s[i+1] == "P":
                s[i] = "D"
    elif i != 0 and s[i] == "?":
        if s[i-1] == "P":
            s[i] = "D"
        elif s[i-1] == "D":
            s[i] = "P"

print("".join(s))

### FIXED CODE ###

s = list(input())
n = len(s)

for i in range(n):
    # if i == 0 and s[i] == "?":
    #     if s[i+1] == "D" or s[i+1] == "?":
    #         s[i] = "P"
    #     else:
    #         if s[i+1] == "P":
    #             s[i] = "D"
    # elif i != 0 and s[i] == "?":
    #     if s[i-1] == "P":
    #         s[i] = "D"
    #     elif s[i-1] == "D":
    #         s[i] = "P"
    if s[i] == "?":
        s[i] = "D"

print("".join(s))
import numpy as np
import itertools as ittr

def test_switch(e_balls, sw, p):
    for i, e_ball in enumerate(e_balls):
        si = sw[eb - 1]
        
        if p[i] != (np.sum(si == 1) % 2):
            return False
    
    return True

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

e_balls = []

for m in range(M):
    i = input().split()
    s = [int(si) for si in i[1:]]
    e_balls.append(s[:])

p = [int(pi) for pi in input().split()]

cnt = 0

for sw in ittr.product([0, 1], repeat = N):
    if test_switch(e_balls, np.array(sw), p):
        cnt += 1

print(cnt)

### FIXED CODE ###

import numpy as np

def test_switch(e_balls, sw, p):
    for i, e_ball in enumerate(e_balls):
        eb = np.asarray(e_ball)
        si = sw[eb - 1]
        
        if p[i] != (np.sum(si == 1) % 2):
            return False
    
    return True

def transform_sw(sw):
    if sw[0] == 0:
        sw[0] = 1
        return sw
    else:
        sw[0] = 0

    for i, s in enumerate(sw[1:]):
        if s == 0:
            sw[i + 1] = 1
            return sw
        elif s == 1:
            sw[i + 1] = 0
    
    return sw


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

e_balls = []

for m in range(M):
    i = input().split()
    s = [int(si) for si in i[1:]]
    e_balls.append(s[:])

p = [int(pi) for pi in input().split()]

sw = np.array([0 for _ in range(N)])
cnt = 0

while np.sum(sw == 1) != N:
    if test_switch(e_balls, sw, p):
        cnt += 1
    transform_sw(sw)

if test_switch(e_balls, sw, p):
        cnt += 1

print(cnt)
n = int(input())
a = list(map(int, input().split()))
c = [0] * (n + 1)
for i in range(n):
  c[i + 1] = c[i] + a[i]
d = {}
for i in range(1, n + 1):
  if c[i] not in d:
    d[c[i]] = 0
  d[c[i]] += 1
result = d[0]
for k in d:
  if d[k] != 1:
    result += d[k] * (d[k] - 1) // 2
print(result)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
c = [0] * (n + 1)
for i in range(n):
  c[i + 1] = c[i] + a[i]
d = {}
for i in range(1, n + 1):
  if c[i] not in d:
    d[c[i]] = 0
  d[c[i]] += 1
result = 0
if 0 in d:
  result += d[0]
for k in d:
  if d[k] != 1:
    result += d[k] * (d[k] - 1) // 2
print(result)
import fraction


def main():
    a = list(map(int, input().split()))
    b = fraction.gcd(a[0], a[1])
    c = b
    for i in range(a[2]-1):
        while True:
            c -= 1
            if b % c == 0:
                break
    print(c)


main()

### FIXED CODE ###

import fractions


def main():
    a = list(map(int, input().split()))
    b = fractions.gcd(a[0], a[1])
    c = b
    for i in range(a[2]-1):
        while True:
            c -= 1
            if b % c == 0:
                break
    print(c)


main()
a, b = map(int, input().split())
s = input()

if s[a+1] == "-":
    s2 = s[:a+1] + s[a+2:]
    for i in range(a+b):
        if s2[i] not in ["0","1","2","3","4","5","6","7","8","9"]:
            print("No")
            break
    else:
        print("Yes")
else:
    print("No")

### FIXED CODE ###

print(48 - int(input()))
a,b = map(int,input().split())
t = b - a
n = [1]
x = 1

for i in range(2,999):
  x = i + x
  n.append(x)

else:
  for j in range(0,len(n) + 1):
    if n[j+1] - n[j] == t:
      break
print(n[j] - a)
    

### FIXED CODE ###

a,b=map(int,input().split())
total=0
for i in range(1,b-a+1):
  total+=i
print(total-b)
h = input()
w = input()
h_a = h // 2
w_a = w // 2
if((h_a == 0) & (w_a == 0)):
  print(h_a * w_a)
elif((h_a == 1) & (w_a == 0)):
  print((h_a+1) * w_a)
elif((h_a == 0) & (w_a == 1)):
  print(h_a * (w_a + 1))
elif((h_a == 1) & (w_a == 1)):
  print((h_a + 1) * (w_a + 1))

### FIXED CODE ###

h,w = map(int,input().split())
h_a = h % 2
w_a = w % 2
h_b = h // 2 
w_b = w // 2 
if(h == 1 or w == 1):
  print(1)

elif((h_a == 0) & (w_a == 0)):
  print(h_b * w)
elif((h_a == 1) & (w_a == 0)):
  print(w_b * h)
elif((h_a == 0) & (w_a == 1)):
  print(h_b * w)
elif((h_a == 1) & (w_a == 1)):
  print((h_b + 1) * (w_b + 1) + h_b * w_b)