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

import sys
input = sys.stdin.readline

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

sumA = sum(A)
countA = len(A)
ans = 0
for i in range(N,-1,-1):
    if i != N:
        sumA -= A[i]
        countA -= 1
    time = sumA
    
    if time > K:
        count = 0
    else:
        count = countA
    j=0
    while time+B[j] <=K:
        count += 1
        time += B[j]
        j += 1
        if j >= M:
            break
        #print(count,time,B[i])
    ans = max(ans,count)
print(ans)
        



### FIXED CODE ###

import sys
input = sys.stdin.readline

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

time = sum(A)
count = len(A)
ans = 0
j=0
for i in range(N,-1,-1):
    if i != N:
        time -= A[i]
        count -= 1
    if time>K:
        continue
    if time <= K and j<M:
        while time+B[j] <=K:
            time +=B[j]
            j +=1
            count +=1
            if j >=M:
                break
    ans = max(ans,count)
print(ans)
### BUGGY CODE ###

def d_practical_skill_test(H, W, D, A, Q, I):
    import numpy
    a = numpy.array(A)
    tmp = []
    for i in range(D):
        i += 1 + D
        t = [0]
        while i <= H * W:
            j, k = numpy.where(a == i)
            l, m = numpy.where(a == i - D)
            j, k = j[0], k[0]
            l, m = l[0], m[0]
            t.append(t[-1] + abs(j - l) + abs(k - m))
            i += D
        tmp.append(t)
    ans=[]
    for l, r in I:
        l = l - 1
        r = r - 1
        start = l % D
        ans.append(str(tmp[start][r // D] - tmp[start][l // D]))
    return '\n'.join(ans)

H,W,D = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(H)]
Q = int(input())
I = [[int(i) for i in input().split()] for j in range(Q)]
print(d_practical_skill_test(H, W, D, A, Q, I))

### FIXED CODE ###

def d_practical_skill_test(H, W, D, A, Q, I):
    # クエリが1-indexedなため、配列もそれに従う
    px = [0 for _ in range(H * W + 1)]
    py = [0 for _ in range(H * W + 1)]  # (px[i],py[j])にAijの値が入っている
    d = [0 for _ in range(H * W + 1)]
    for i in range(H):
        for j in range(W):
            px[A[i][j]] = i
            py[A[i][j]] = j
    for i in range(D + 1, H * W + 1):
        d[i] = d[i - D] + abs(px[i] - px[i - D]) + abs(py[i] - py[i - D])
    ans = []
    for l, r in I:
        ans.append(str(d[r] - d[l]))
    return '\n'.join(ans)

H,W,D = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(H)]
Q = int(input())
I = [[int(i) for i in input().split()] for j in range(Q)]
print(d_practical_skill_test(H, W, D, A, Q, I))
### BUGGY CODE ###

from collections import deque
import copy

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

edge_list = [set() for i in range (N)]


for i in range (M):
    A,B = map(int,input().split())
    edge_list[A-1].add(B-1)
    edge_list[B-1].add(A-1)

for i in range (N):
    d =deque(edge_list[i])
    while d:
        a = d.popleft()
        el = copy.copy(edge_list[a])
        for j in range (len(edge_list[a])):
            aj = el.pop()
            if (aj not in edge_list[i]) and i != aj:
                edge_list[i].add(aj)
                d.append(aj)


edge_list = list(map(len,edge_list))

print(max(edge_list)+1)


### FIXED CODE ###

class UnionFind:
    def __init__ (self,n):
        self.parent = [i for i in range (n)]
        self.height = [0 for _ in range (n)]

    def get_root(self,i):
        if self.parent[i] == i:
            return i
        else:
            self.parent[i] = self.get_root(self.parent[i])
            return self.parent[i]

    def unite(self,i,j):
        root_i = self.get_root(i)
        root_j = self.get_root(j)
        if root_i != root_j:
            if self.height[root_i] < self.height[root_j]:
                self.parent[root_i] = root_j
            else:
                self.parent[root_j] = root_i
                if self.height[root_i] == self.height[root_j]:
                    self.height[root_i] += 1

    def is_in_group(self,i,j):
        if self.get_root(i) == self.get_root(j):
            return True
        else:
            return False

def main():
    N,M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range (M):
        A,B = map(lambda x: int(x)-1,input().split())
        uf.unite(A,B)

    check = [0]*N
    for i in range(N):
        check[uf.get_root(i)] += 1
    print(max(check))


main()
### BUGGY CODE ###

import sys
from heapq import heappush, heappop
from collections import defaultdict

N=input()
nl=[ [ ] for i in range(N+1) ] 

hq=[]
for i in range(N):
	L=map(int, sys.stdin.readline().split())
	for j in range(i+1,N):
		heappush( hq, (L[j],i+1,j+1) )


ans=0
for n in range(N-1):
	cost,x,y=heappop( hq )
	nl[x].append( (cost,y) )
	nl[y].append( (cost,x) )
	ans+=cost



def dij(start,end):
	#d=[ float("inf")  for i in range(N+1) ] 
	d=defaultdict(lambda: float("inf")) 
	d[start]=0
	q=[]
	heappush( q, start )	#u: chouten
	while q:
		fro=heappop(q)
		for cost, to in nl[fro]:
			alt=d[fro]+cost
			if d[to]>alt:
				d[to]=alt
				heappush(q,to)
	return d[end]

while hq:
	input_cost,x,y=heappop( hq )
	cost=dij(x,y)
	if cost < input_cost:
		print -1
		quit()
	elif input_cost<cost:
		nl[x].append( (input_cost,y) )
		nl[y].append( (input_cost,x) )
		ans+=input_cost

print ans

### FIXED CODE ###

import numpy as np
N = input()
A = [np.array(map(int,raw_input().split()), dtype=np.int64) for _ in [0]*N]
inf = 10**10
for i in range(N):
    A[i][i] = inf
#print A


result = 0
for i in range(N-1):
    for j, d1 in enumerate(A[i][i+1:], start=i+1):
	#print i,j,A[i], A[j], np.min(A[i]+A[j]),d1
        d2 = np.min(A[i]+A[j])
        if d1 >= d2:
            if d1 > d2:
                print(-1)
                exit()
        else:
            result += d1
print(result)
### BUGGY CODE ###



def frog2(h, K):
    c = [None] * len(h)
    c[0] = 0
    c[1] = abs(h[0] - h[1])
    for i in range(2, len(c)):
        c[i] = min(c[i-k] + abs(h[i-k] - h[i]) for k in range(1, min(i+1, K+1)))
    return c[-1]


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

### FIXED CODE ###

import sys
import numpy as np
def frog2(h, K):
    c = np.full_like(h, 0)
    c[0] = 0
    c[1] = abs(h[0] - h[1])
    for i in range(2, len(c)):
        k = min(i, K)
        c[i] = np.min(c[i-k:i] + abs(h[i-k:i] - h[i]))
        # c[i] = min(c[i-k] + abs(h[i-k] - h[i]) for k in range(1, min(i+1, K+1)))
    return c[-1]


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

print(frog2(h, K))
### BUGGY CODE ###

N = int(input())
X = int(input(),2)
def A(xi):
    if xi == 0:
        return 0
    else:
        return A(xi%(str(bin(xi)).count('1'))) + 1
for i in range(1,N+1):
    xi = X ^ (1<<(N-i))
    print(A(xi))

### FIXED CODE ###

N=int(input())
X=input()
Y=int(X,2)
Z=Y
C=X.count('1')
if C==1:
  for i in range(N):
    if X[i]=='1':
      print(0)
    elif i==N-1:
      print(2)
    else:
      print(1)
  exit()
Y,Z=Y%(C+1),Z%(C-1)
def f(x):
  if x==0:
    return 0
  return 1+f(x%bin(x).count('1'))
 
for i in range(N):
  if X[i]=='1':
    print(1+f((Z-pow(2,N-i-1,C-1))%(C-1)))
  else:
    print(1+f((Y+pow(2,N-i-1,C+1))%(C+1)))
### BUGGY CODE ###

N, A, B = map(int, input().split(' '))
 
blue = 0
if N!=0 and A!=0:
    for i in range(int(N/(A+B))+1):
        if i==int(N/(A+B)):
            if N%(A+B) <= A:
                blue += N%(A+B)
            else:
                blue += A 
        else:
            blue += A

print(blue)

### FIXED CODE ###

N, A, B = map(int, input().split(' '))
 
blue = 0
if N!=0 and A!=0:    
    blue = A *int(N/(A+B))
    if N%(A+B) <= A:
        blue += N%(A+B)
    else:
        blue += A 
print(blue)
### BUGGY CODE ###

# EDPC B Frog 2
N, K = map(int, input().split())
H = list(map(int,input().split()))

cost = [float("inf")]*N
cost[0] = 0
cost[1] = abs(H[1]-H[0])

for i in range(2,N):
    for k in range(1,min(K,i)+1):
        cost[i] = min(cost[i], cost[i-k]+abs(H[i]-H[i-k]))

print(cost[N-1])


### FIXED CODE ###

# EDPC B Frog 2
N, K = map(int, input().split())
H = list(map(int,input().split()))

cost = [float("inf")]*N
cost[0] = 0
cost[1] = abs(H[1]-H[0])

for i in range(2,N):
    for k in range(1,min(K,i)+1):
        cost[i] = min(cost[i], cost[i-k]+abs(H[i]-H[i-k]))

print(cost[N-1])
### BUGGY CODE ###

def solve():
	N, *A = map(int, open(0).read().split())

	top = [A[0]]
	for i in range(1, N):
		da_min = 10**9
		color = -1
		for j in range(len(top)):
			da = A[i] - top[j]
			if da > 0:
				if da_min > da:
					da_min = da
					color = j
		if color != -1:
			top[color] = A[i]
		else:
			top.append(A[i])

	print(len(top))


if __name__ == '__main__':
	solve()

### FIXED CODE ###

from bisect import bisect_left
from collections import deque


def solve():
	N, *A = map(int, open(0).read().split())

	top = deque([A[0]])
	for a in A[1:]:
		if top[0] >= a:
			top.appendleft(a)
		else:
			index = bisect_left(top, a)
			top[index-1] = a
	
	print(len(top))


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

from collections import deque
import sys
input2 = sys.stdin.readline()

s=list(input2)
Q=int(input())

d=deque(s)
d.pop()
cnt=0
for i in range(Q):
    tmp=list(input())
    if tmp[0] == "1":
        cnt+=1
    else:
        if tmp[2] == "1":
            if (cnt > 0) and (cnt%2 == 0):
                d.appendleft(tmp[4])
                cnt=0
            elif cnt > 0:
                d.reverse()
                d.appendleft(tmp[4])
                cnt=0
            else:
                d.appendleft(tmp[4])
        else:
            if (cnt > 0) and (cnt%2 == 0):
                d.append(tmp[4])
                cnt=0
            elif cnt > 0:
                d.reverse()
                d.append(tmp[4])
                cnt=0
            else:
                d.append(tmp[4])
if (cnt > 0) and (cnt%2 != 0):
    d.reverse()
ans=list(d)
answer="".join(ans)
print(answer)

### FIXED CODE ###

from collections import deque
import sys
input2 = sys.stdin.readline()

s=list(input2)
Q=int(input())
direction=0
d=deque(s)
d.pop()

for i in range(Q):
    tmp=list(input())
    if tmp[0] == "1":
        if direction == 0:
            direction = 1
        else:
            direction = 0
    else:
        if tmp[2] == "1":
            if direction == 0:
                d.appendleft(tmp[4])
            else:
                d.append(tmp[4])
        else:
            if direction == 0:
                d.append(tmp[4])
            else:
                d.appendleft(tmp[4])
if direction==1:
    d.reverse()
ans=list(d)
answer="".join(ans)
print(answer)
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n
rage=range #lol
for i in rage(1,n):
    if i<k: dp[i]+=min([dp[i-j]+abs(h[i]-h[i-j]) for j in rage(1,i+1)])
    else: dp[i]+=min([dp[i-j]+abs(h[i]-h[i-j]) for j in rage(1,k+1)])
print(dp[-1])


### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n
rage=range #lol
for i in rage(1,n):
    dp[i]=10**9;
    for j in range(1,k+1):
        if i-j<0:
            break;
        dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[-1])
### BUGGY CODE ###

def main():
    N, M = list(map(int, input().split(' ')))
    s = M // N
    r = M % N
    while True:
        if r%s == 0:
            print(s)
            break
        if s > r:
            a = (s-r)//N
        else:
            a = 1
        if a == 0:
            a = 1
        s -= a
        r += a*N



if __name__ == '__main__':
    main()

### FIXED CODE ###

import math

def main():
    N, M = list(map(int, input().split(' ')))
    s = min(math.ceil(math.sqrt(M)), M//N)
    ret = []
    while s > 0:
        if M%s == 0:
            a = M//s
            ret.append(a)
            ret.append(s)
        s -= 1
    print(max([s for s in ret if s <= M//N]))



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

N = int(input())
alist = list(map(int, input().split()))
Sum_a = 0
for i in range(N):
  Sum_j = 0
  for j in range(i+1, N):
    Sum_j += alist[j]
  Sum_j = Sum_j
  Sum_a += (alist[i] * Sum_j) % (1e9+7)
print(int(Sum_a % (1e9+7)))

### FIXED CODE ###

N = int(input())
alist = list(map(int, input().split()))
import numpy as np
Sum_a = 0
Sum_j_list = np.cumsum(alist)
for i in range(N-1):
  Sum_j = int((Sum_j_list[N-1] - Sum_j_list[i]) % int(1e9+7))
  Sum_a += (alist[i] * Sum_j) % int(1e9+7)
print(int(Sum_a % int(1e9+7)))
### BUGGY CODE ###

a, b, c, k = input().split()
a, b, c, k = int(a), int(b), int(c), int(k)
result = 0

if a == k:
    result = a
else:
    for i in range(k):
        if a != 0:
            result = result + 1
            a = a - 1
        elif a == 0 and b != 0:
            #result変わらず
            b = b - 1
        elif a == 0 and b == 0 and c != 0:
            result = result - 1
            c = c - 1
        else:
            break

print(result)


### FIXED CODE ###

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

if a >= k:
    print(k)
    exit()

if k-a-b <= 0:
    print(a)
    exit()

print(a-(k-a-b))
### BUGGY CODE ###

def password():
    for i in range(10):
        for j in range(10):
            for k in range(10):
                yield [str(i), str(j), str(k)]


n = int(input())
s = input()

ans = 0
for perm in password():
    j = 0
    for i in range(n):
        if perm[j] == s[i]:
            j += 1
            if j >= len(perm):
                break
    if j >= len(perm):
        ans += 1

print(ans)


### FIXED CODE ###

def password():
    for i in range(10):
        for j in range(10):
            for k in range(10):
                yield [str(i), str(j), str(k)]


n = int(input())
s = input()

ans = 0
for perm in password():
    if perm[0] in s:
        a = s.find(perm[0])
        if perm[1] in s[a + 1 :]:
            b = s[a + 1 :].find(perm[1])
            if perm[2] in s[a + 1 :][b + 1 :]:
                ans += 1

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

n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7

s = [0]*n
for i in range(n):
    s[i] = sum(a[i+1:]) % mod
# print(s)

ans = 0
for i in range(n-1):
    ans += a[i]*s[i] % mod

print(ans % mod)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7

s = [0]*n
for i in reversed(range(1,n)):
    s[i-1] = s[i] + a[i]
# print(s)

ans = 0
for i in range(n-1):
    ans += a[i]*s[i] % mod

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

n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
mod=10**9+7
dp=[[0]*(m+1) for i in range(n+1)]
for i in range(n+1):
  dp[i][0]=1
for i in range(m+1):
  dp[0][i]=1
for i in range(n):
  for j in range(m):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1]
    else:
      dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1]-dp[i][j]
    dp[i+1][j+1]%=mod
print(dp[-1][-1])

### FIXED CODE ###

n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
mod=10**9+7
dp=[[0]*(m+1) for i in range(n+1)]
for i in range(n+1):
  dp[i][0]=1
for i in range(m+1):
  dp[0][i]=1
for i in range(n):
  for j in range(m):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1]
    else:
      dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1]-dp[i][j]
    dp[i+1][j+1]%=mod
print(dp[-1][-1])
### BUGGY CODE ###

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

max_cnt = 0
for tmp_i in range(N-1):
    i = tmp_i
    cnt = 0
    flag = True
    while flag:
        if i+1<N and data[i]>=data[i+1]:
            cnt += 1
            i += 1
        else:
            flag = False
    if max_cnt<cnt:
        max_cnt=cnt

print(max_cnt)


### FIXED CODE ###

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

i = 0
max_cnt = 0
while i<N-1:
    # i = tmp_i
    cnt = 0
    flag = True
    while flag:
        if i+1<N and data[i]>=data[i+1]:
            cnt += 1
            i += 1
        else:
            flag = False
            i += 1
    # tmp_i+=1
    if max_cnt<cnt:
        max_cnt=cnt

print(max_cnt)
### BUGGY CODE ###

n=int(input())
listl = [int(i) for i in input().split()]

listl.sort(reverse=True)

#print(listl)
ans=0
"""if n==3:
	if listl[0]>=listl[1]+listl[2]:
		ans=0
	else:
		ans=1
else:"""
for i in range(n-2):
	for j in range(i+1,n-1):
		for k in range(j+1,n):
		#	print(listl[i],listl[j],listl[k])
			if listl[i]<listl[j]+listl[k]:
				ans=ans+1
			else:
				break	
print(ans)
				 
	

### FIXED CODE ###

n=int(input())
listl = [int(i) for i in input().split()]

"""listl.sort(reverse=True)

#print(listl)
	ans=0
for i in range(n-2):
	for j in range(i+1,n-1):
		if listl[j]<=(listl[i]/2):
			break
		for k in range(j+1,n):

			if listl[i]<listl[j]+listl[k]:
				ans=ans+1
			else:
				break	

print(ans)"""
from bisect import bisect_right				 
listl.sort()

ans=0

for i in range(n-1,1,-1):
	a=listl[i]
	for j in range(i-1,0,-1):
		b=listl[j]
		c=bisect_right(listl,a-b)
		#print(c)
		num = j-c
		if num>0:
			ans+=num
print(ans)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

for i in range(m):
  a, b = map(int, input().split())
  uf.union(a - 1, b - 1)

ans = 0
for i in range(n):
  ans = max(ans, len(uf.members(i)))

print(ans)

### FIXED CODE ###

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size,子なら親の頂点
n, m = map(int, input().split())
par = [-1]*n

for i in range(m):
  a, b = map(int, input().split())
  unite(a - 1, b - 1)

ans = 0
for i in range(n):
  ans = max(ans, size(i))

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

n, m = map(int, input().split())
a = [0] * m
b = [0] * m
for i in range(m):
    a[i], b[i] = map(int, input().split())

first = []
second = []
for i in range(m):
    if a[i] == 1:
        first.append(b[i])

    if b[i] == n:
        second.append(a[i])
ans = 'IMPOSSIBLE'
for i in first:
    if i in second:
        ans = 'POSSIBLE'
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
a = [0] * m
b = [0] * m
first = set()
second = set()
for i in range(m):
    a[i], b[i] = map(int, input().split())
    if a[i] == 1:
        first.add(b[i])
    if b[i] == n:
        second.add(a[i])


ans = 'IMPOSSIBLE'
if first & second:
    ans = 'POSSIBLE'
print(ans)
### BUGGY CODE ###

import numpy as np
import sys
from bisect import bisect_right, bisect_left

readline = sys.stdin.readline

# 入力にかかる最大計算量O(NlogN)：クイックソート
N = int(input())
A = np.array(readline().split(), np.int64)
# A_sort = np.sort(A)
A_sum = sum(A)
Q = int(input())
BC = np.array([np.array(readline().split(), np.int64) for n in range(Q)], np.int64)
# BC[N][0,1]

# ここの計算量O(N(logN + logN))
for q in range(Q):
    # A = [BC[q][1] if x==BC[q][0] else x for x in A]
    # A[bisect.bisect_left(A, BC[q][0]):bisect.bisect_right(A, BC[q][0])] = BC[q][1]
    '''
    plus_num = BC[q][1] - BC[q][0]
    left = bisect_left(A_sort, BC[q][0])
    right = bisect_right(A_sort, BC[q][0])
    plus_multiple = right - left
    A_sort[left:right] = BC[q][1]
    A_sort = np.sort(A_sort)
    '''
    plus_num = BC[q][1] - BC[q][0]
    plus_multiple = np.count_nonzero(A == BC[q][0])
    A[A==BC[q][0]] = BC[q][1]

    A_sum = A_sum + plus_num*plus_multiple
    print(A_sum)



### FIXED CODE ###

import numpy as np
import sys
from bisect import bisect_right, bisect_left

readline = sys.stdin.readline

# 入力にかかる最大計算量O(NlogN)：クイックソート
N = int(input())
A = np.array(readline().split(), np.int64)
num_array = np.zeros(10**5, np.int64)
for n in A:
    num_array[n-1] += 1

# A_sort = np.sort(A)
A_sum = sum(A)
Q = int(input())
BC = np.array([np.array(readline().split(), np.int64) for n in range(Q)], np.int64)
# BC[N][0,1]

# ここの計算量O(N(logN + logN))
for q in range(Q):
    # A = [BC[q][1] if x==BC[q][0] else x for x in A]
    # A[bisect.bisect_left(A, BC[q][0]):bisect.bisect_right(A, BC[q][0])] = BC[q][1]
    '''
    plus_num = BC[q][1] - BC[q][0]
    left = bisect_left(A_sort, BC[q][0])
    right = bisect_right(A_sort, BC[q][0])
    plus_multiple = right - left
    A_sort[left:right] = BC[q][1]
    A_sort = np.sort(A_sort)
    '''

    '''
    plus_num = BC[q][1] - BC[q][0]
    plus_multiple = np.count_nonzero(A == BC[q][0])
    A[A==BC[q][0]] = BC[q][1]
    '''

    plus_num = BC[q][1] - BC[q][0]
    plus_multiple = num_array[BC[q][0] - 1]
    # リスト内の要素数の更新
    num_array[BC[q][1]- 1] += num_array[BC[q][0] - 1]
    num_array[BC[q][0] - 1] = 0

    A_sum = A_sum + plus_num*plus_multiple
    print(A_sum)
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = map(int, input().split())
Q = int(input())

counter = Counter(A)
for i in range(Q):
  b, c = map(int, input().split())
  count_b = counter[b]
  counter[b]-= count_b
  counter[c] += count_b
  print(sum([k*v for k, v in counter.items()]))

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Q = int(input())

counter = Counter(A)
ans = sum(A)
for i in range(Q):
  b, c = map(int, input().split())
  count_b = counter[b]
  counter[b] -= count_b
  counter[c] += count_b
  ans = ans - b*count_b + c*count_b
  print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0

for i in range(k+1):
    for j in range(k+1):
        for m in range(k+1):
            if i+j+m == s:
                count += 1

print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0

for i in range(k+1):
    for j in range(k+1):
        t = s - (i + j)
        if 0 <= t and t <= k:
            count += 1

print(count)
### BUGGY CODE ###

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

result = 0

for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k == S:
                result += 1

print(result)

### FIXED CODE ###

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

result = 0

for i in range(K+1):
    for j in range(K+1):
        if 0 <= S - (i + j) <= K:
            result +=1
print(result)