Harryxun/stf_run huggingface dataset:
MOD = 998244353
MAX = int(3e5 + 1)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD


def main():
    N, A, B, K = map(int, input().split())
    ans = 0
    for x in range(N+1):
        By = K - x * A
        if By >= 0 and By % B == 0:
            y = By // B
            tmp1 = FACT[N] * INV[x] * INV[N-x] % MOD
            tmp2 = FACT[N] * INV[y] * INV[N-y] % MOD
            ans = (ans + tmp1 * tmp2) % MOD
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

MOD = 998244353
MAX = int(3e5 + 1)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD


def main():
    N, A, B, K = map(int, input().split())
    ans = 0
    # solve Ax + By = K
    for x in range(N+1):
        By = K - x * A
        if By >= 0 and By % B == 0 and By <= B * N:
            y = By // B
            tmp1 = FACT[N] * INV[x] * INV[N-x] % MOD
            tmp2 = FACT[N] * INV[y] * INV[N-y] % MOD
            ans = (ans + tmp1 * tmp2) % MOD
    print(ans)

if __name__ == "__main__":
    main()
h,w = map(int,input().split())
for i in range(h):
  s = input().split()
  if 'snuke' in s:
    ans = ord('A') + s.index('snuke')
    print(ans + str(i+1))
    break


### FIXED CODE ###

h,w = map(int,input().split())
for i in range(h):
  s = input().split()
  if 'snuke' in s:
    ans = ord('A') + s.index('snuke')
    print(chr(ans) + str(i+1))
from scipy.special import comb
e,o = map(int,input().split())

base1 = comb(e, 2, exact=True)
base2 = comb(o, 2, exact=True)

print(base1+base2)

### FIXED CODE ###

e,o = map(int,input().split())
cte = (e*(e-1))//2
cto = (o*(o-1))//2
print(cte+cto)
A,B,C,D = map(int,input().split())

while True:
  C -= B
  if C<=0:
    print('Yes')
    break
  A -= D
  if <=0:
    print('No')
    break

### FIXED CODE ###

A,B,C,D = map(int,input().split())

while True:
  C -= B
  if C<=0:
    print('Yes')
    break
  A -= D
  if A<=0:
    print('No')
    break
import pandas as pd

x = -1
y = -1
S = list(input())
for i in range(1, len(S)-1):
    for j in range(i+2, len(S)+1):
        s = pd.DataFrame(S[i:j])
        if s[0].value_counts()[0] > (len(s)//2):
            x = i
            y = j
            break
print(x, y)

### FIXED CODE ###

# 回答を見て

x = -1
y = -1
S = list(input())

for i in range(len(S)-1):
    if S[i] == S[i+1]:
        x = i+1
        y = x+1
        break
    elif i+2<=len(S)-1:
        if S[i] == S[i+2]:
            x = i+1
            y = x+2
            break
        else:
            pass
    else:
        pass
print(x, y)
_,s,*a=map(int,open(0).read().split())
c,i,*d=[0]*s*4
for a in a:
 for j in range(s,0,-1):d[a+j]+=d[j]
 d[a]-=~i;c+=d[s];i+=1
print(c%(998244353))

### FIXED CODE ###

n,s,*a=map(int,open(0).read().split())
d=[0]*3001
c=0
for i,a in enumerate(a):
    for j in range(s-a,0,-1):d[a+j]+=d[j]
    d[a]-=~i
    c+=d[s]
print(c%(998244353))
n = int(input())
a = input().split()
a = [int(i) for i in a]

candidate = a[n:len(a)+1]
print(sum([candidate[i] for i in (1 , 2n+1, 2)]))

### FIXED CODE ###

n = int(input())
a = input().split()
a = [int(i) for i in a]
a = sorted(a)
 
candidate = a[n:len(a)+1]
print(sum([candidate[i] for i in range(0, 2*n, 2)]))
N = int(input())
lst = list(map(int, input().split()))

dic1, dic2 = dict(), dict()
for i, x in enumerate(lst):
    dic = dic1 if  i%2 == 0 else dic2
    if x not in dic.keys():
        dic[x] = 1
    else:
        dic[x] += 1
#print (type(dic1))
dic1 =sorted(dic1.items(), key = lambda x:x[1])[::-1]
dic2 =sorted(dic2.items(), key = lambda x:x[1])[::-1]

#print (type(dic2))
#print (dic1)
#print (dic2)

if dic1[0][0] != dic2[0][0]:
    print (N-dic1[0][1]-dic2[0][1])
#elif len(dic1) == 1 and len(dic2) == 1:
#    print (n//2)
#elif len(dic1) == 1:
#    print (N-dic1[0][1]-dic2[1][1])
#elif len(dic2) == 1:
#    print (N-dic1[1][1]-dic2[0][1])
else:
    print (mix(N-dic1[0][1]-dic2[1][1], N-dic1[1][1]-dic2[0][1]))


### FIXED CODE ###

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

dic1, dic2 = dict(), dict()
#dic1[0] = 0
#dic2[0] = 0
for i, x in enumerate(lst):
    dic = dic1 if  i%2 == 0 else dic2
    if x not in dic.keys():
        dic[x] = 1
    else:
        dic[x] += 1
#print (type(dic1))
dic1 =sorted(dic1.items(), key = lambda x:x[1])[::-1]
dic2 =sorted(dic2.items(), key = lambda x:x[1])[::-1]

#print (type(dic2))
#print (dic1)
#print (dic2)

if dic1[0][0] != dic2[0][0]:
    print (N-dic1[0][1]-dic2[0][1])
elif len(dic1) == 1 and len(dic2) == 1:
    print (N//2)
elif len(dic1) == 1:
    print (N-dic1[0][1]-dic2[1][1])
elif len(dic2) == 1:
    print (N-dic1[1][1]-dic2[0][1])
else:
    print (min(N-dic1[0][1]-dic2[1][1], N-dic1[1][1]-dic2[0][1]))
#nの約数列挙
def devisor(n):
    ans = []
    if n == 1:return [1]
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            if i != n//i:
                ans.append(i)
                ans.append(n//i)
            else:
                ans.append(i)
            

    return ans       

#n個の正数の積でmになる場合の数
def cnt(n,m):
    ans = 0
    if n == 1:return 1
    s = devisor(m)
    for i in s:
        ans += cnt(n-1,m//i)
    return ans


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

### FIXED CODE ###

def fctr(n):
    f = []
    c = 0
    for i in range(2,int(n**0.5)+1):
        while n%i==0:
            c+=1
            n = n//i
        if c!=0:
            f.append([i,c])
            c = 0

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

    return f

def combination(n,r):
    r = min(r,n-r)
    result = 1
    for i in range(n-r+1,n+1):
        result *= i
    for i in range(1,r+1):
        result //= i
    return result

mod = 10**9 + 7
N,M = list(map(int,input().split()))
ans = 0
s = fctr(M)

for i in s:
    if ans == 0:
        ans = combination(N-1+i[1],i[1]) % mod
    else:
        ans = (ans*combination(N-1+i[1],i[1]))%mod

if M != 1:         
    print(ans)
else:
    print('1')
def make_tree(node):
    for i in tree_list[node]:
        if i != tree_dic[node]["p"]:
            tree_dic[node]["c"].append(i)
            tree_dic[i]["p"] = node
            make_tree(i)

n, q = map(int, input().split())
tree_list = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    tree_list[a-1].append(b-1)
    tree_list[b-1].append(a-1)

tree_dic = {} #tree_dic = {i:{p:j, c:[k, l]}}
for i in range(n):
    tree_dic[i] = {"p": None, "c": [], "x": 0}

make_tree(0)

for i in range(q):
    p, x = map(int, input().split())
    tree_dic[p-1]["x"] += x
# print(tree_dic)

x_list = [0 for _ in range(n)]

import queue
next_visit = queue.Queue()
next_visit.put(0)
while not next_visit.empty():
    i = next_visit.get()
    tmp = tree_dic[i]["x"]
    if i != 0:
        tmp += x_list[tree_dic[i]["p"]]
    x_list[i] = tmp
    for j in tree_dic[i]["c"]:
        next_visit.put(j)

for i in x_list:
    print(i, end=" ")

### FIXED CODE ###

n, q = map(int, input().split())
tree_candidate = [[] for _ in range(n)]

for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree_candidate[a].append(b)
    tree_candidate[b].append(a)

tree = [[] for _ in range(n)]

app = set([0])

import queue
next = queue.Queue()
next.put(0)
# print(tree_candidate)
while not next.empty():
    i = next.get()
    for j in tree_candidate[i]:
        if not j in app:
            tree[i].append(j)
            app.add(j)
            next.put(j)

cnts = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, input().split())
    cnts[p-1] += x
    # print(x, p, tree[p-1], cnts)

next = queue.Queue()
next.put(0)

while not next.empty():
    i = next.get()
    for j in tree[i]:
        cnts[j] += cnts[i]
        next.put(j)

for i in cnts:
    print(i, end=' ')
n=int(input())
s=list(input())

for i in range(n-1):
    i_set=set(s[i+1:])

    for j in i_set:
        j_ind=s.index(j)
        s_i=s[i+1:]
        j_set=set(s_i[s_i.index(j)+1:])
        [ans.add(s[i]+j+k) for k in j_set]

print(len(ans))

### FIXED CODE ###

n = int(input())

s = input()

ans = set()
for i in range(10):
    a = s.find(str(i))
    if a == -1:
        continue
    for j in range(10):
        b = s.find(str(j), a+1)
        if b == -1:
            continue
        for k in range(10):
            if s.find(str(k), b+1) != -1:
                ans.add(str(i)+str(j)+str(k))
print(len(ans))
N , M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a,b=[0],[0]
for i in range(N): a.append(a[i] + A[i])
for i in range(M): b.append(b[i] + B[i])
ans,j=0,0
for i in range(N+1):
  if a[i]>K:
    break
  while b[j] <= K - a[i]:
    j += 1
  ans = max(ans, i+j-1)
print(ans)

### FIXED CODE ###

N , M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a,b=[0],[0]
for i in range(N): a.append(a[i] + A[i])
for i in range(M): b.append(b[i] + B[i])
ans,j=0,M
for i in range(N+1):
  if a[i]>K:
    break
  while b[j] > K - a[i]:
    j -= 1
  ans = max(ans, i+j)
print(ans)
def g():
    from collections import defaultdict
    N, M = map(int, input().split())
    xy = defaultdict(list)
    memo = defaultdict(list)
    for _ in range(M):
        x, y = map(int, input().split())
        xy[x].append(y)

    def g2(x):
        if x in memo:
            return memo[x]
        else:
            r = 0
            for ny in xy[x]:
                r = max(r, g2(ny) + 1)
            memo[x] = r
        return r

    ans = [g2(i) for i in range(1, N + 1)]
    return max(ans)


if __name__ == '__main__':
    ans = g()
    print(ans)

### FIXED CODE ###

def g():
    from collections import defaultdict
    import sys

    sys.setrecursionlimit(10 ** 6)
    N, M = map(int, input().split())
    xy = defaultdict(list)
    memo = {}
    for _ in range(M):
        x, y = map(int, input().split())
        xy[x].append(y)

    def g2(x):
        if x in memo:
            return memo[x]
        else:
            r = 0
            for ny in xy[x]:
                r = max(r, g2(ny) + 1)
            memo[x] = r
        return r

    ans = 0
    for i in range(1, N + 1):
        ans = max(ans, g2(i))
    return ans


if __name__ == '__main__':
    ans = g()
    print(ans)
for i in range(400):

    if card == 'a':
        SA = SA[1:]
        card = SA[0]
    elif card == 'b':
        SB = SB[1:]
        card = SB[0]
    elif card == 'c':
        SC =SC[1:]
        card = SC[0]

    if len(SA)==1 and card=='a':
        print('A')
        break
    elif len(SB)==1 and card=='b':
        print('B')
        break
    elif len(SC)==1 and card=='c':
        print('C')
        break

### FIXED CODE ###

SA, SB, SC = [input() for i in range(3)]
SA = SA + '0'
SB = SB + '0'
SC = SC + '0'

card = SA[0]
SA = SA[1:]

for i in range(303):
    if SA == '0' and card == 'a':
        print('A')
        break
    elif SB == '0' and card == 'b':
        print('B')
        break
    elif SC == '0' and card == 'c':
        print('C')
        break
    
    if card == 'a':
        card = SA[0]
        SA = SA[1:]
    elif card == 'b':
        card = SB[0]
        SB = SB[1:]
    elif card == 'c':
        card = SC[0]
        SC = SC[1:]
import math
n, m = map(long, input().split())
kotae=1

for i in range(1,long(math.sqrt(m))+1):
	if m%i==0:
		if i*n<=m:
			kotae=max(kotae, i)
		if (m/i)*n<=m:
			kotae=max(kotae, int(m/i))
print(kotae)

### FIXED CODE ###

import math
n, m = map(int, input().split())
kotae=1

for i in range(1,int(math.sqrt(m))+1):
	if m%i==0:
		if i*n<=m:
			kotae=max(kotae, i)
		if (m//i)*n<=m:
			kotae=max(kotae, m//i)
print(kotae)
h=[a,b]
map(int(input(),h))
print(a*b,(a+b)*2)
  

### FIXED CODE ###

a,b=map(int,input().split())
print(a*b,(a+b)*2)
import math
abcd = input().split(" ")
a = int(abcd[0])
b = int(abcd[1])
c = int(abcd[2])
d = int(abcd[3])
cd = (c*d)//math.gcd(c, d)
print(b-a+1 - ((b+1)//c - a//c) - ((b+1)//d - a//d) + ((b+1)//cd - a//cd))


### FIXED CODE ###

import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
abcd = input().split(" ")
a = int(abcd[0])
b = int(abcd[1])
c = int(abcd[2])
d = int(abcd[3])
cd = lcm(c, d)
print(b-a-(b//c-((a-1)//c + 1))-(b//d - ((a-1)//d + 1))+(b//cd-((a-1)//cd + 1)))
a,b=map(int, sinput().split())
if a >= 13:
    print(b)
elif 6 <= a and a <= 12:
    print(b/2)
else:
    print(0)


### FIXED CODE ###

a,b=map(int, input().split())
if a <= 5:
    print(0)
elif 6 <= a and a <= 12:
    print(int(b/2))
else:
    print(b)
s=list(map(int,list(input())))
n=len(s)
ans=0
for i in range(1<<(n-1)):
"""ここで既に、n-1個の文字間のうち、どこに+を入れるかが決まる。入れるところにはbitが立ち(その桁が1となる)、入れないところにはbitが立たない(その桁が0となる)"""
    S=s[0]
    for j in range(n-1):
        if i & (1<<j): #bitが立っている時
            S+="+"+s[j+1]
        else: #bitが立っていない時
            S+=s[j+1]
    ans+=eval(S)
print(ans)

### FIXED CODE ###

s=list(input())
n=len(s)
ans=0
for i in range(1<<(n-1)):

    """
    ここで既に、n-1個の文字間のうち、どこに+を入れるかが決まる。入れるところにはbit
    が立ち(その桁が1となる)、入れないところにはbitが立たない(その桁が0となる)
    """

    S=s[0]
    for j in range(n-1):
        if i & (1<<j): #bitが立っている時
            S+="+"+s[j+1]
        else: #bitが立っていない時
            S+=s[j+1]
    ans+=eval(S)
print(ans)
import numpy as np

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


class Node:
    def __init__(self, parent):
        self.parent = parent
        self.leaf = []
        self.score = 0

    def add_score(self, score):
        self.score += score
        for l in self.leaf:
            l.add_score(score)


tree = {1: Node(None)}
tmp = np.array([list(map(int, input().split())) for _ in range(N-1)])
for i in np.argsort(tmp[:, 0]):
    p, c = tmp[i][0], tmp[i][1]
    if p not in tree:
        tree[p] = Node(None)
    if c not in tree:
        tree[c] = tree[p]
    tree[p].leaf.append(tree[c])

for p, x in [tuple(map(int, input().split())) for _ in range(Q)]:
    tree[p].add_score(x)

print(' '.join([str(t.score) for t in tree.values()]))


### FIXED CODE ###

from collections import defaultdict

N, Q = map(int, input().split())
d = defaultdict(list)

for _ in range(N - 1):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

c = defaultdict(int)

for _ in range(Q):
    p, x = map(int, input().split())
    c[p] += x

ans = [0 for i in range(N)]
que = [(1, 0, -1)]
while len(que) > 0:
    tmp = []
    for v, x, par in que:
        x += c[v]
        ans[v - 1] = str(x)
        for w in d[v]:
            if w != par:
                tmp.append((w, x, v))
    que = tmp

print(*ans)
a,b=map(int,input().split())
c,d=map(int,input().split())
play_day=a-(c+d)
if play_day>0:
    print(play_day)
else:
    print(-1)

### FIXED CODE ###

a,b=map(int,input().split())
C=list(map(int,input().split()))
play_day=a-sum(C)
if play_day>=0:
    print(play_day)
else:
    print("-1")
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

# ループを見つける(5000), 一周のスコアを確認
is_visit = [0 for _ in range(n)]
loop = []

def search(i, j):
    if is_visit[i] == 0:
        is_visit[i] = j
        l.append(i)
        search(p[i]-1, j)

loop_id = 1
for i in range(n):
    l = []
    search(i, loop_id)
    if len(l) != 0:
        loop.append(l)
        loop_id += 1
# print(loop)
# print(is_visit)

ans = [0 for _ in range(n)]
for i in range(n):
    # i からはじめて最大スコア
    l = loop[is_visit[i]-1] # 所属するループ
    tmp1 = 0 # ループによるスコア
    tmp_k = k
    s = 0
    for j in range(len(l)):
        s += c[l[j]]
    if s > 0 and k > len(l):
        # 回るほどお得
        tmp1 += s*(tmp_k//len(l))
        tmp_k -= tmp_k//len(l)*len(l)
    else:
        tmp_k -= tmp_k//len(l)*len(l)
        if tmp_k == 0:
            tmp_k = len(l)
    pointer = p[i]
    tmp2 = [c[pointer-1] for _ in range(tmp_k)] # 愚直に進んだ点数
    if tmp_k != 0:
        for j in range(1, tmp_k):
            # k回目までの累積和で最大を求める
            pointer = p[pointer-1]
            tmp2[j] = tmp2[j-1] + c[pointer-1]
    # print(i, l, s, tmp_k, tmp1, tmp2)
    if len(tmp2) != 0:
        ans[i] = tmp1 + max(tmp2)
    else:
        ans[i] = tmp1
# print(ans)
print(max(ans))


### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

# ループを見つける(5000), 一周のスコアを確認
is_visit = [0 for _ in range(n)]
loop = []

def search(i, j):
    if is_visit[i] == 0:
        is_visit[i] = j
        l.append(i)
        search(p[i]-1, j)
    else:
        pass

loop_id = 1
for i in range(n):
    l = []
    search(i, loop_id)
    if len(l) != 0:
        loop.append(l)
        loop_id += 1
# print(loop)
# print(is_visit)
s_list = [0 for _ in range(len(loop))]
for i in range(len(s_list)):
    l = loop[i]
    s = 0
    for j in range(len(l)):
        s += c[l[j]]
    s_list[i] = s

ans = [0 for _ in range(n)]
for i in range(n):
    # i からはじめて最大スコア
    l = loop[is_visit[i]-1] # 所属するループ
    tmp1 = 0 # ループによるスコア
    tmp_k = k
    s = s_list[is_visit[i]-1]
    if s > 0 and k > len(l):
        # 回るほどお得で一周より回れる
        tmp1 += s*(tmp_k//len(l)-1)
        tmp_k -= (tmp_k//len(l)-1)*len(l)
    elif s <= 0 and k > len(l):
        tmp_k -= (tmp_k//len(l)-1)*len(l)
        if tmp_k == 0:
            tmp_k = len(l)
    pointer = p[i]
    tmp2 = [c[pointer-1] for _ in range(tmp_k)] # 愚直に進んだ点数
    if tmp_k != 0:
        for j in range(1, tmp_k):
            # k回目までの累積和で最大を求める
            pointer = p[pointer-1]
            tmp2[j] = tmp2[j-1] + c[pointer-1]
    # print(i, l, s, tmp_k, tmp1, tmp2)
    if len(tmp2) != 0:
        ans[i] = tmp1 + max(tmp2)
    else:
        ans[i] = tmp1
# print(ans)
print(max(ans))
import math

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

MOD = 10**9 + 7

def make_fact_list(n, MOD):
    # make factorial list from 0 to n
    fact = [0] * (n+1)
    inv = [0] * (n+1)
    factinv = [0] * (n+1)

    fact[0]=fact[1]=1
    inv[1]=1
    factinv[0]=factinv[1]=1

    for i in range(2,n+1):
        fact[i] = fact[i-1] * i % MOD
        inv[i] = MOD - (( inv[MOD % i] *  (MOD // i)) % MOD )
        factinv[i] = factinv[i-1] * inv[i] % MOD
    
    return fact, factinv

def cbn(n_f, k, MOD, fact = [], factinv = []):
    if len(fact) == 0 and len(factinv) == 0:
        fact, factinv = make_fact_list(n, MOD)
    return fact[n] * factinv[n-k] * factinv[k] % MOD

def power_with_mod(x, n, MOD):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return power_with_mod(x*x % MOD , n // 2, MOD) % MOD
    else:
        return x * power_with_mod(x * x % MOD, n // 2, MOD) % MOD

s = power_with_mod(2, n, MOD)-1

fact, factinv = make_fact_list(b, MOD)

s -= cbn(n, a, MOD, fact, factinv)
s -= cbn(n, b, MOD, fact, factinv)


print(s)

### FIXED CODE ###

import math

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

MOD = int(1e9) + 7

s = pow(2, n, MOD)-1

def cbn(n, a, MOD):
    x = 1
    for i in range(a):
        x = (x * (n-i)) % MOD

    y = math.factorial(a) % MOD
    return x * pow(y, MOD-2, MOD) %MOD

s = (s- cbn(n, a, MOD)) %MOD
s = (s- cbn(n, b, MOD)) %MOD


print(s)
i = 1
while 1:
  x = input()
  if !x: break
  print('Case ' i ': ' x)
  i += 1


### FIXED CODE ###

i,x = 1,input()
while x != "0":
  print('Case '+str(i)+': '+x)
  i,x = i+1,input()
def bis_right(lis,dev):
    a=0
    b=len(lis)
    while a<b:
        c=(a+b)//2
        if lis[c]>dev:
            b=c
        else:
            a=c+1
    if lis[a]<=dev:
        return a
    return a-1



n=int(input())
l=[int(x) for x in input().split()]
l.sort()
s=0
for a in range(n-2):
    for b in range(a+1,n-1):
        c=bis_right(l[b+1:],l[a]+l[b]-1)
        s+=c+1
print(s)

### FIXED CODE ###

def bis_right(lis,dev):
    a=0
    b=len(lis)-1
    while a<b:
        c=(a+b)//2
        if lis[c]>dev:
            b=c
        else:
            a=c+1
    if lis[a]<=dev:
        return a
    return a-1



n=int(input())
l=[int(x) for x in input().split()]
l.sort()
s=0
for a in range(n-2):
    for b in range(a+1,n-1):
        c=bis_right(l[b+1:],l[a]+l[b]-1)
        s+=c+1
print(s)
def back_oturigation(fee, coin_values, coin_nums):
    oturi = coin_values[0] * coin_nums[0] \
            + coin_values[1] * coin_nums[1] \
            + coin_values[2] * coin_nums[2] \
            + coin_values[3] * coin_nums[3] \
            - fee
    use_coins = [0] * len(coin_values)
    no_use_coins = [0] * len(coin_values)


    for i in range(len(coin_values) - 1, -1, -1):
        no_use_coins[i] = int(oturi / coin_values[i])
        oturi = oturi - (coin_values[i] * no_use_coins[i])


    for i in range(0, len(use_coins), 1):
        use_coins[i] = coin_nums[i] - no_use_coins[i]
        if use_coins[i] > 0:
            print(str(coin_values[i]) + ' ' + str(use_coins[i]))


if __name__ == "__main__":
    total_fee = int(input('total_fee:'))

    while (total_fee != 0):
        coins = input('total_coins:')
        coins = coins.split(' ')  # 10, 50, 100, 500????????§????????????
        coins = [int(coin) for coin in coins]
        coin_values = [10, 50, 100, 500]
        back_oturigation(total_fee, coin_values, coins)

### FIXED CODE ###

import math
def back_oturigation(fee, coin_values, coin_nums):
    """
    1. ?????????????????????????????????£??????????????????
    2. 1????????????????????????????????????????????????????????????
       ????????????§?????????????????????-> ??°?????????????????????¶???????????????????
    3. 2?????????????????????°?????????????????????????????????????????????
    """
    # 1.
    oturi = coin_values[0] * coin_nums[0] \
            + coin_values[1] * coin_nums[1] \
            + coin_values[2] * coin_nums[2] \
            + coin_values[3] * coin_nums[3] \
            - fee

    use_coins = [0] * len(coin_values)
    no_use_coins = [0] * len(coin_values)
 
    # 2.
    for i in range(len(coin_values) - 1, -1, -1):
        no_use_coins[i] = int(oturi / coin_values[i])
        oturi = oturi - (coin_values[i] * no_use_coins[i])
 
    # 3.
    for i in range(0, len(use_coins), 1):
        use_coins[i] = coin_nums[i] - no_use_coins[i]
        if use_coins[i] > 0:
            print(str(coin_values[i]) + ' ' + str(use_coins[i]))
 
if __name__ == "__main__":
    first = True
    while (True):
        total_fee = int(input(''))
        if total_fee == 0:
            break
        if first:
            first = False
        else:
            print('')
        coins = input('')
        coins = coins.split(' ')  # 10, 50, 100, 500?????????§????????????
        coins = [int(coin) for coin in coins]
        coin_values = [10, 50, 100, 500]
        back_oturigation(total_fee, coin_values, coins)
N,K = (i for i in input().split())
K = int(K)
X = list(N)
if X[K-1] == 'A':
    X[K-1] = 'a'
if X[K-1] == 'B':
    X[K-1] = 'b'
if X[K-1] == 'C':
    X[K-1] = 'c'
print(''.join(X))

### FIXED CODE ###

T,K = (i for i in input().split())
N = input()
K = int(K)
X = list(N)
if X[K-1] == 'A':
    X[K-1] = 'a'
if X[K-1] == 'B':
    X[K-1] = 'b'
if X[K-1] == 'C':
    X[K-1] = 'c'
print(''.join(X))
a,b,c,d=map(int,input().split())

def calc_div_num(a,b,x):
  return b//x - (a-1)//x

num_c = b//c - (a-1)//c
num_d = b//d - (a-1)//d

import numpy as np
lcd = np.lcd(c,d)
num_lcd = b//lcd - (a-1)//lcd

result = b-a+1 - (num_c+num_d-num_lcd)
print(result)

### FIXED CODE ###

a,b,c,d=map(int,input().split())

def calc_div_num(a,b,x):
  return b//x - (a-1)//x

num_c = calc_div_num(a, b, c)
num_d = calc_div_num(a, b, d)

import numpy as np
lcd = np.lcm(c, d)
num_lcd = calc_div_num(a, b, lcd)

result = b-a+1 - (num_c+num_d-num_lcd)
print(result)
n = int(input())
arr = list(map(int, input().split()))

su = sum(arr)

q = int(input())
for i in range(q):
	b,c = map(int, input().split())
    si = su -b + c
    print(si)


### FIXED CODE ###

def ad(a,bank):
	if a not in bank:
		bank[a] = 1
	else:
		bank[a] += 1

def rp(a,b,bank):
	ans = 0
	if a in bank:
		t = bank[a]
		ans = t
		bank[a] = 0
		if b not in bank:
			bank[b] = t
		else:
			bank[b] += t
		
	return ans
# your code goes here
n = int(input())
arr = list(map(int, input().split()))

bank = dict()
su = 0

for a in arr:
	ad(a,bank)
	su += a

q = int(input())
for i in range(q):
	b,c = map(int, input().split())
	t = rp(b,c,bank)
	if b in bank:
		su = su - (t*b) + (t*c)
	
	print(su)