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

from collections import deque
from fractions import gcd
from functools import reduce
n = int(input())
v = list(map(int,input().split()))
v = deque(v)

def gcd_list(numbers):
    return reduce(gcd, numbers)

ans = 1
for i in range(n):
    v1 = v.popleft()
    g = gcd_list(v)
    v.append(v1)
    ans = max(ans,g)
print(ans)




### FIXED CODE ###

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

def gcd(a,b):
  while b != 0:
    a, b = b, a % b
  return a

l_ans = [0] * n
g = 0
for i in range(1, n):
    g = gcd(g, v[i-1])
    l_ans[i] = g
r_ans = [0] * n
g = 0
for i in range(1, n):
    g = gcd(g, v[n-i])
    r_ans[i] = g
r_ans.reverse()
ans = 1
for i in range(n):
    ans = max(ans, gcd(l_ans[i], r_ans[i]))
print(ans)
### BUGGY CODE ###

N=int(input())
S=[input() for i in range(N)]
G=[[] for i in range(N)]
for i in range(N):
    for j in range(N):
        if S[i][j]=="1":
            G[i].append(j)
q=[0]
dist=[-1 for i in range(N)]
dist[0]=0
while(q):
    r=q.pop()
    for p in G[r]:
        if dist[p]==-1:
            dist[p]=1-dist[r]
            q.append(p)
for i in range(N):
    for j in G[i]:
        if dist[i]==dist[j]:
            print(-1)
            exit()
#possible
#print(G)
d=[[10**9 for i in range(N)] for i in range(N)]
for i in range(N):
    for j in G[i]:
        d[i][j]=1
    d[i][i]=0

for k in range(N):
    for i in range(N):
        for j in range(N):
            if d[i][j]>d[i][k]+d[k][j]:
                d[i][j]=d[i][k]+d[k][j]
ans=2
for i in range(N):
    for j in range(N):
        ans=max(ans,d[i][j]+1)
print(ans)


### FIXED CODE ###

N=int(input())
S=[input() for i in range(N)]
G=[[] for i in range(N)]
for i in range(N):
    for j in range(N):
        if S[i][j]=="1":
            G[i].append(j)
q=[0]
dist=[-1 for i in range(N)]
dist[0]=0
while(q):
    r=q.pop()
    for p in G[r]:
        if dist[p]==-1:
            dist[p]=1-dist[r]
            q.append(p)
for i in range(N):
    for j in G[i]:
        if dist[i]==dist[j]:
            print(-1)
            exit()
#possible
#print(G)
d=[[10**9 for i in range(N)] for i in range(N)]
for i in range(N):
    for j in G[i]:
        d[i][j]=1
    d[i][i]=0

for k in range(N):
    for i in range(N):
        for j in range(N):
            if d[i][j]>d[i][k]+d[k][j]:
                d[i][j]=d[i][k]+d[k][j]
ans=2
for i in range(N):
    for j in range(N):
        ans=max(ans,d[i][j]+1)
print(ans)
### BUGGY CODE ###

n = int(input())

ans = 0
for i in range(1, 10**6+1):
    if n % i == n//i:
        ans += i

syou = n // 10**6

i = 10**6 + 1
while True:
    if syou != n//i:
        break
    else:
        if n % i == n//i:
            ans += i
    i += 1

syou = n//i

for i in range(1, syou+1):
    if (n-i) % i != 0:
        continue
    else:
        okiniiri = (n-i) // i
        if n % okiniiri == i:
            ans += okiniiri 

print(ans)

### FIXED CODE ###

n = int(input())

ans = 0
for i in range(1, 10**6+1):
    if n % i == n//i:
        ans += i

if n <= 10**6:
    print(ans)
    exit()
  
syou = n // 10**6

i = 10**6 + 1
while True:
    if syou != n//i or i >= n:
        break
    else:
        if n % i == n//i:
            ans += i
    i += 1

syou = n//i

for i in range(1, syou+1):
    if (n-i) % i != 0:
        continue
    else:
        okiniiri = (n-i) // i
        if n % okiniiri == i:
            ans += okiniiri 

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

n, p = map(int, input().split())
s = input()

ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    # dp = [0] * p
    # dp[0] = 1
    # tmp = 0
    # for i in range(n)[::-1]:
    #     tmp = (int(s[i]) * pow(10, n - i - 1, p) + tmp) % p
    #     print(tmp)
    #     ans += dp[tmp]
    #     dp[tmp] += 1
    # print(dp)

    # ベースの考え方。https://drken1215.hatenablog.com/entry/2020/03/08/020200
    # 素数pで割ったあまりは、0, 1, 2, ... p - 1になる。
    # 例えば、s=152467, p=3とする
    # 0 mod 3 = 0 (単独でも1つになるので、便宜上加える)
    # 7 mod 3 = 1
    # 67 mod 3 = 1
    # 467 mod 3 = 2
    # 2467 mod 3 = 1
    # 52467 mod 3 = 0
    # 152467 mod 3 = 1
    # となる。
    # 例えば、x mod 3 = 1について、考える。これは、7, 67, 2467, 152467の4つある。
    # これから、67 - 7 = 60で、3で割り切れる。2467 - 7 = 2560で、3で割り切れる。
    # このように、4つのうち2つを組み合わせれば、あまりの数が同じなので、p(3)で割り切れる組み合わせ
    # を作ることができる。
    # 467 mod 3 = 2については、あまりが2はコレしかないので、組み合わせることはできず、0となる。
    # また、あまりが2のものと、あまりが1のもの2個で組み合わせることはできない。なぜなら、
    # 467-67-7で組み合わせたところで、67と7が互いに相殺してしまうし、結果も393という、sの中に存在しない文字になるからである。
    # 基本はこれであり、下記のようになるが、これでは遅い。
    # dp = [0] * p
    # dp[0] = 1
    # tmp = 0
    # for i in range(n)[::-1]:
    #     tmp = (int(s[i:])) % p
    #     dp[tmp] += 1
    # for i in dp:
    #     ans += nCr(i, 2)
    dp = [0] * p
    dp[0] = 1
    tmp = 0
    for i in range(n)[::-1]:
        tmp = (int(s[i:])) % p
        ans += dp[tmp]
        dp[tmp] += 1
print(ans)

'''
6 3
152467
'''

### FIXED CODE ###

from collections import defaultdict
n, p = map(int, input().split())

s = input()
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    tmp = 0
    d = defaultdict(int)
    d[0] = 1
    for i in range(n)[::-1]:
        tmp += int(s[i]) * pow(10, n - i - 1, p)
        tmp %= p
        ans += d[tmp]
        d[tmp] += 1
print(ans)
### BUGGY CODE ###

# ABC134-E

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

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l1=[I() for _ in range(n)]

  l1.reverse()
  l2=[0]*n

  c=1

  # print(l1)
  for i,x in enumerate(l1):
    # print(l2)
    if l2[i]==0:
      l2[i]=i+1
    for j in range(i,n):
      y=l1[j]

      if c==n-1:
        return max(l2)

      if x>y and l2[j]==0:
        c+=1
        l2[j]=i+1
        x=y

  return max(l2)

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  _l=[I() for _ in range(n)]
  l=collections.deque()

  for A in _l:
    if len(l)==0:
      l.append(A)
      continue

    lv=l[0]
    rv=l[-1]
    if rv<A:
      l[-1]=A
      continue
    if A<=lv:
      l.appendleft(A)
      continue

    li=0
    ri=len(l)-1
    while ri-li>1:
      mi=(ri+li)//2
      if l[mi]<A:
        li=mi
      else:
        ri=mi

    l[li]=A

  # print(l)
  return len(l)

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

K,S=map(int,input().split())
ans=0
for i in range(S+1):
  for j in range(S+1-i):
    if 0<=i<=K and 0<=j<=K and 0<=S-i-j<=K:
      ans+=1
print(ans)      

### FIXED CODE ###

K,S=map(int,input().split())
ans=0
for i in range(S+1):
  for j in range(S+1-i):
    if 0<=i<=K and 0<=j<=K and 0<=S-i-j<=K:
      ans+=1
print(ans)
### BUGGY CODE ###

N=int(input())
A=[int(input()) for _ in range(N)]
A=list(map(A.count, set(A)))
ans=0
for a in A:
    if a%2:ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
A=[int(input()) for _ in range(N)]
d={}
for a in A:d[a]=0
for a in A:d[a]+=1
cnt=0
for i in d:
    if d[i]%2:cnt+=1
print(cnt)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
lr_list = list()
for _ in range(m):
    lr_list.append(list(map(int, input().split())))

card_list = [i for i in (1, n + 1)]

set_list = list()
for l, r in lr_list:
    set_list.append({i for i in range(l, r + 1)})

u = set.intersection(*set_list)
print(len(u))


### FIXED CODE ###

n, m = list(map(int, input().split()))
# lr_list = list()
l_list = list()
r_list = list()
for _ in range(m):
    l, r = list(map(int, input().split()))
    l_list.append(l)
    r_list.append(r)
    # lr_list.append(list(map(int, input().split())))

min_r = min(r_list)
max_l = max(l_list)
if max_l <= min_r:
    print(min_r - max_l + 1)
else:
    print(0)
### BUGGY CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

N,M=list(map(int,input().split()))
mn = M//N
ml = M%N
if ml == 0:
    print(mn)
    exit()
ans = 0
for i in range(mn+1,0,-1):
    if i < ans:
        break
    tmp = math.gcd(i,M-i*(N-1))
    ans = max(ans,tmp)
print(ans)


### FIXED CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

N,M=list(map(int,input().split()))
mn = M//N
ml = M%N
if ml == 0:
    print(mn)
    exit()
ans = 0
for i in range(mn+1,0,-1):
    if i < ans:
        break
    tmp = math.gcd(i,M-i*(N-1))
    ans = max(ans,tmp)
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N = int(input())
arr = list(map(int, input().split()))
GCD = 0
max_GCD = 0

for i in range(N):
    GCD = gcd(*(arr[0:i] + arr[i + 1::]))
    if max_GCD < GCD:
        max_GCD = GCD
print(max_GCD)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import fractions

N = int(input())
arr = list(map(int, input().split()))
L = [0]
R = [0]
B = []

for i in range(N):
    L.append(fractions.gcd(arr[i], L[i]))
    R.append(fractions.gcd(arr[N - i - 1], R[i]))
for i in range(N):
    B.append(fractions.gcd(L[i],R[N - i - 1]))
print(max(B))
### BUGGY CODE ###

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

if 0 in a:
  ans = 0
else:
  ans = 1
  for item in a:
    ans = ans * item
  if ans > 1000000000000000000:
    ans = -1
print(ans)


### FIXED CODE ###

def main():
  N = int(input())
  A = list(map(int, input().split()))
  
  if 0 in A:
    print(0)
    return
  
  prod = 1
  for a in A:
    prod *= a
    if prod > 1000000000000000000:
      print(-1)
      return
  print(prod)
  
main()
### BUGGY CODE ###

N, P = map(int, input().split())
ans = 1
def main(n, p):
  global ans
  for i in range(2, int(p**(2/n)+1)):
    t = i**n
    if p % t == 0:
      ans *= i
      return main(n, p//t)
  return ans

print(main(N, P))

### FIXED CODE ###

N, P = map(int, input().split())
ans = 1
def main(n, p):
  if n == 1:
    return P
  global ans
  for i in range(2, int(p**(2/n))):
    t = i**n
    if p % t == 0:
      ans *= i
      return main(n, p//t)
  return ans

print(main(N, P))
### BUGGY CODE ###

import sys


N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
for i in range(N):
    print(A.index(i+1) +1, end =' ')

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in range(n):
  ans[a[i]-1] = i +1
for i in range(n):
  print(ans[i])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

from sys import stdin
    
def calc(n, s):
    s2 = [ c == '#' for c in s]
    total = sum(s2)
    ans =[2*sum(s2[:i])+n-i-total for i in range(n+1)]
    return min(ans)

def main():
    n = int(stdin.readline().rstrip())
    s = stdin.readline().rstrip()
    ans = calc(n, s)
    print(ans)
    
if __name__=='__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-

from sys import stdin
    
def calc(n, s):
    s2 = [ c == '#' for c in s]
    total = sum(s2)
    _min = min(total, n-total)
    tr = 0
    for i,c in enumerate(s2):
        if c:
            tr += 1
        op = 2*tr+n-(i+1)-total
        if op < _min:
            _min = op

    return _min

def main():
    n = int(stdin.readline().rstrip())
    s = stdin.readline().rstrip()
    ans = calc(n, s)
    print(ans)
    
if __name__=='__main__':
    main()
### BUGGY CODE ###

Q=int(input())

PN=[-1]*(10**5+1)
PN[0]=0
PN[1]=0

def PN_chk(n):
    if PN[n]==1:return True
    elif PN[n]==0:return False
    else:
        for i in range(2,int(int(n**0.5)+1)):
            if n%i==0:
                PN[n]=0
                return False
        PN[n]=1
        return True


chk=[-1]*(10**5+1)

def YN(n):
    if chk[n]==1:return True
    elif chk[n]==0:return False
    else:
        if PN_chk(n)==True and PN_chk((n+1)//2)==True:
            chk[n]=1
            return True
        else:
            chk[n]=0
            return False

for i in range(Q):
    ans=0
    l,r=map(int,input().split())
    for j in range(l,r+1,2):
        if YN(j):ans+=1
    print(ans)




### FIXED CODE ###

import bisect

def PN(N):
    for i in range(2,int(N**0.5)+1):
        if N%i==0:
            return False
    return True

N=[3]
for i in range(5,100001,2):
    if PN(i) and PN((i+1)//2):
        N.append(i)

Q=int(input())

for i in range(Q):
    l,r=map(int,input().split())
    ln1=bisect.bisect_left(N,l)
    ln2=bisect.bisect_right(N,l)
    rn1=bisect.bisect_left(N,r)
    rn2=bisect.bisect_right(N,r)
    if ln1==ln2 and rn1==rn2:
        print(rn1-ln1)
    elif ln1==ln2 or rn1==rn2:
        print(rn1-ln2+1)
    else:
        print(rn1-ln2+2)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import queue

def solve(H: int, W: int, black):
    Q = queue.Queue()
    marked = [[0] * W for h in range(H)]
    qlen = 0
    for h, w in black:
        Q.put((h, w))
        qlen += 1
        marked[h][w] = 1
    
    count = 0
    while not Q.empty():
        flag = False
        for _ in range(qlen):
            h, w = Q.get()
            qlen -= 1
            for hh, ww in [(h-1, w), (h+1, w), (h, w-1), (h, w+1)]:
                if 0 <= hh <= H-1 and 0 <= ww <= W-1 and marked[hh][ww] == 0:
                    flag = True
                    Q.put((hh, ww))
                    qlen += 1
                    marked[hh][ww] = 1
        if flag:
            count += 1
    print(count)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    black = []
    for h in range(H):
        line = next(tokens)
        for w, c in enumerate(line):
            if c == '#':
                black.append((h, w))
    solve(H, W, black)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

inf = float('inf')

def solve(H: int, W: int, A: "List[str]"):
    dist = [[inf] * W for h in range(H)]
    for h in range(1, H):
        for w in range(1, W):
            if A[h][w] == '#':
                dist[h][w] = 0
            else:
                dist[h][w] = min(dist[h-1][w], dist[h][w-1]) + 1
    
    dmax = 0
    for h in range(H-1, -1, -1):
        for w in range(W-1, -1, -1):
            if A[h][w] == '#':
                dist[h][w] = 0
            elif h+1 <= H-1 and w+1 <= W-1:
                dist[h][w] = min(dist[h][w], min(dist[h+1][w], dist[h][w+1]) + 1)
            elif w+1 == W and h+1 <= H-1:
                dist[h][w] = min(dist[h][w], dist[h+1][w] + 1)
            elif h+1 == H and w+1 <= W-1:
                dist[h][w] = min(dist[h][w], dist[h][w+1] + 1)
            dmax = max(dist[h][w], dmax)
    print(dmax) 
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, A)

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

N=int(input().split(" ")[0])
put=input().split(" ")
A=[]
for i in range(N):
    A.append(int(put[i]))

p=[A[0]]
for i in range(1,N-1):
    if A[i-1]<A[i] and A[i]>A[i+1]:
        p.append(A[i])
    elif A[i-1]>A[i] and A[i]<A[i+1]:
        p.append(A[i])

p.append(A[N-1])

x=0
t=1
for i in range(len(p)):
    k=i+1
    y=0
    while k<=(len(p)-1):
        if y< p[k]-p[i]:
            y=p[k]-p[i]
        k+=1
    if x<y:
        x=y
        t=1
    elif x==y:
        t=t+1

print(t)        

### FIXED CODE ###

nt=input().split(" ")
N=int(nt[0])
T=int(nt[1])


a=input().split(" ")
int_a=[]
maxlist=[]
for i in range(N):
    int_a.append(int(a[i]))

reva=int_a
reva.reverse()
max=0
for i in range(N):
    if reva[i]>max:
        max=reva[i]
    maxlist.append(max)

maxlist.reverse()
int_a.reverse()


max=0
count=1
for i in range(N):
    if maxlist[i]-int_a[i]>max:
        count=1
        max=maxlist[i]-int_a[i]
    elif maxlist[i]-int_a[i]==max:
        count+=1

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

import sys
import numpy as np
from numba import njit
input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**10, N)

dp = np.zeros((n, 10**5+1), np.int32)
dp[0, vws[0][1]:] = vws[0][0]
for i in range(1, n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])

@njit("(i4[::], i4[::], i4, i4)", cache = True)
def func(vs, ws, V, L):
    bits = np.arange(1 << len(vs))
    values = np.zeros_like(bits, np.int32)
    weights = np.zeros_like(bits, np.int32)
    for i in range(len(vs)):
        indices = np.nonzero(np.bitwise_and(bits, 1<<i))
        values[indices] += vs[i]
        weights[indices] += ws[i]

    mask = (weights <= L)     
    print(np.amax(dp[V][L - weights[mask]] + values[mask]))


Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V][L])
    else:
        vws_choose = []
        while V >= n:
            vws_choose.append(vws[V])
            V = (V-1) // 2
        vs, ws = zip(*vws_choose)
        func(np.array(vs, np.int32), np.array(ws, np.int32), V, L)


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    ret = 0
    for v, w in zip(values, weights):
        if w <= L:
            ret = max(dp_[L - w] + v, ret)
    return ret

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))
### BUGGY CODE ###

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

ans = 0
for x in range(n+1):
    y = int(a * x / b) - a * int(x / b)
    if x == 0 or y > ans:
        ans = y


print(ans)


### FIXED CODE ###

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

def floor(x):
    return int(a * x / b) - a * int(x / b)

if n >= b-1:
    ans = floor(b-1)
else:
    ans = floor(n)

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

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
H = [0]+list(map(int, input().split()))
dp = [[[10**18]*(N+1) for _ in range(K+1)] for _ in range(2)]
dp[0][0][0] = 0

for i in range(N):
    for j in range(K+1):
        for k in range(N+1):
            dp[(i+1)%2][j][k] = 10**18
            
    for j in range(K+1):
        for k in range(N+1):
            if j+1<=K:
                dp[(i+1)%2][j+1][k] = min(dp[(i+1)%2][j+1][k], dp[i%2][j][k])
            
            dp[(i+1)%2][j][i+1] = min(dp[(i+1)%2][j][i+1], dp[i%2][j][k]+max(0, H[i+1]-H[k]))

ans = 10**18

for i in range(K+1):
    for j in range(N+1):
        ans = min(ans, dp[N%2][i][j])
    
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
H = [0]+list(map(int, input().split()))
dp = [[[10**18]*(N+1) for _ in range(K+1)] for _ in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    for j in range(K+1):
        for k in range(N+1):
            if j+1<=K:
                dp[i+1][j+1][k] = min(dp[i+1][j+1][k], dp[i][j][k])
            
            dp[i+1][j][i+1] = min(dp[i+1][j][i+1], dp[i][j][k]+max(0, H[i+1]-H[k]))

ans = 10**18

for i in range(K+1):
    for j in range(N+1):
        ans = min(ans, dp[N][i][j])
    
print(ans)
### BUGGY CODE ###

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

def gcd(a, b):
	while b:
		a, b = b, a%b
	return a


#これだとTLEする
ans=0
for i in range(N):
	temp=0
	for idx, a in enumerate(A):
		if idx==i:
			continue
		temp=gcd(temp, a)
	ans=max(ans,temp)
print(ans)

### FIXED CODE ###

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

def gcd(a, b):
	while b:
		a, b = b, a%b
	return a

gcd_from_left = [0]*N # 自分のindexは含まないようなもの
gcd_from_right = [0]*N
 
for i in range(1,N):
  gcd_from_left[i] = gcd(A[i-1],gcd_from_left[i-1])
  gcd_from_right[N-1-i] = gcd(A[N-i],gcd_from_right[N-i])
  
ans = 0
 
for a,b in zip(gcd_from_left, gcd_from_right):
  x = gcd(a,b)
  if ans < x:
    ans = x
    
print(ans)
### BUGGY CODE ###

from itertools import accumulate
N, M, K = map(int,input().split())
A_list = [0] + list(map(int,input().split()))
B_list = [0] + list(map(int,input().split()))
A_sums_list = list(accumulate(A_list))
B_sums_list = list(accumulate(B_list))

for n in range(N + 1):
    if A_sums_list[n] > K:
        break
    A_max = n
for m in range(M + 1):
    if B_sums_list[m] > K:
        break
    B_max = m
ans = max(A_max, B_max)

for i in reversed(range(A_max + 1)):
    for j in reversed(range(B_max + 1)):
        if i + j > ans:
            if A_sums_list[i] + B_sums_list[j] <= K:
                ans = i + j
                break
        else:
            break
print(ans)

### FIXED CODE ###

import itertools
n, m, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))

sa = list(itertools.accumulate(a))
sb = list(itertools.accumulate(b))

output = 0
j = m
for i in range(n + 1):
    if sa[i] > k:
        break
    while sa[i] + sb[j] > k:
        j -= 1
    if output < i + j:
        output = i + j
print(output)
### BUGGY CODE ###

import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools
from collections import Counter

def main():
    n = int(input())
    a = list(map(int, input().split()))
    l = [0]*10**5
    for i in a:
        l[i-1] += i
    q = int(input())
    for i in range(q):
        b,c = map(int, input().split())
        l[c-1] += l[b-1]//b*c
        l[b-1] = 0
        print(sum(l))



if __name__=="__main__":
    main()


### FIXED CODE ###

import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools
from collections import Counter

def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = sum(a)
    l = [0]*10**5
    for i in a:
        l[i-1] += 1
    q = int(input())
    for i in range(q):
        b,c = map(int, input().split())
        ans += (c-b)*l[b-1]
        l[c-1] += l[b-1]
        l[b-1] = 0
        print(ans)

if __name__=="__main__":
    main()