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

import sys

def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())

    answer = sum(A)
    setA = set(A)
    numNumberList = [0] * 100001

    for Ai in setA:
        numNumberList[Ai] = A.count(Ai)    

    for i in range(Q):
        B, C = list(map(int, sys.stdin.readline().split()))
        answer = answer + (int(C) - int(B)) * numNumberList[B]

        numNumberList[C] = numNumberList[C] + numNumberList[B]
        numNumberList[B] = 0

        print(answer)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())

    answer = sum(A)
    setA = set(A)
    numNumberList = [0] * 100001

    for Ai in A:
        numNumberList[Ai] = numNumberList[Ai] + 1    

    for i in range(Q):
        B, C = list(map(int, sys.stdin.readline().split()))
        answer = answer + (int(C) - int(B)) * numNumberList[B]

        numNumberList[C] = numNumberList[C] + numNumberList[B]
        numNumberList[B] = 0

        print(answer)

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

def search(x,r):
  low = 0
  high = len(r)-1
  mid = (low+high)//2
  while low<=high:
    rr = r[mid]-x
    ll = r[mid+1]-x
    if rr*ll<=0:
      return(abs(rr),abs(ll))
    elif r[mid]-x > 0:
      high = mid
      mid = (low+high)//2
    else:
      low = mid
      mid = (low+high)//2
      

a, b, q = [int(i) for i in input().split()]
s = []
for i in range(a):
	s.append(int(input()))
s = [-float('inf')] + s + [float('inf')]
t = []
for i in range(b):
	t.append(int(input()))
t = [-float('inf')] + t + [float('inf')]
x = []
for i in range(q):
	x.append(int(input()))

for xx in x:
  
  s_l,s_r=search(xx,s)
  t_l,t_r=search(xx,t)
  
  #print(s_l,s_r,t_l,t_r)
  
  #l = max(s_l,t_l)
  #r = max(s_r,t_r)
  if s_l <= t_l:
    l = t_l
    lr = s_l*2 + t_r
  else:
    l = s_l
    lr = t_l*2 + s_r
  if s_r <= t_r:
    r = t_r
    rl = s_r*2 + t_l
  else:
    r = s_r
    rl = t_r*2 + s_l
 
  ans = min(l,r,lr,rl)
  print(ans)
  

### FIXED CODE ###

from bisect import bisect

a, b, q = [int(i) for i in input().split()]
s = []
for i in range(a):
	s.append(int(input()))
s = [-float('inf')] + s + [float('inf')]
t = []
for i in range(b):
	t.append(int(input()))
t = [-float('inf')] + t + [float('inf')]
x = []
for i in range(q):
	x.append(int(input()))

for xx in x:
  
  s_i = bisect(s,xx)
  s_r = abs(xx - s[s_i])
  s_l = abs(xx - s[s_i-1])
  t_i = bisect(t,xx)
  t_r = abs(xx - t[t_i])
  t_l = abs(xx - t[t_i-1])

  
  #print(s_l,s_r,t_l,t_r)
  
  #l = max(s_l,t_l)
  #r = max(s_r,t_r)
  if s_l <= t_l:
    l = t_l
    lr = s_l*2 + t_r
  else:
    l = s_l
    lr = t_l*2 + s_r
  if s_r <= t_r:
    r = t_r
    rl = s_r*2 + t_l
  else:
    r = s_r
    rl = t_r*2 + s_l
 
  ans = min(l,r,lr,rl)
  print(ans)
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline
inf = 10**8
DX = (-1, 0, 1, 0, -1, -1, 1, 1)
DY = (0, 1, 0, -1, -1, 1, -1, 1)
DX = DX[:4]
DY = DY[:4]


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


dist = [[inf]*W for _ in range(H)]
node = deque()
for i in range(H):
    for j in range(W):
        if grid[i][j] == "S":
            node.append((i, j))
            dist[i][j] = 0

# まず一回普通にBFS
memo = []
while node:
    x, y = node.popleft()
    memo.append((x, y))
    d = dist[x][y]
    if d >= K:
        continue
    for dx, dy in zip(DX, DY):
        nx = x + dx
        ny = y + dy
        if nx < 0 or ny < 0 or nx >= H or ny >= W:
            continue
        if grid[nx][ny] == "#":
            continue
        if dist[nx][ny] > d + 1:
            dist[nx][ny] = d + 1
            node.append((nx, ny))


ans = inf
for x, y in memo:
    d = min(x, y, H - x - 1, W - y - 1)
    ans = min(ans, 1 + (d + K - 1) // K)
print(ans)

### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
inf = 10**8
DX = (-1, 0, 1, 0, -1, -1, 1, 1)
DY = (0, 1, 0, -1, -1, 1, -1, 1)
DX = DX[:4]
DY = DY[:4]


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


dist = [[inf]*W for _ in range(H)]
node = deque()
for i in range(H):
    for j in range(W):
        if grid[i][j] == "S":
            node.append((i, j))
            dist[i][j] = 0

# まず一回普通にBFS
memo = []
while node:
    x, y = node.popleft()
    memo.append((x, y))
    d = dist[x][y]
    if d >= K:
        continue
    for dx, dy in zip(DX, DY):
        nx = x + dx
        ny = y + dy
        if nx < 0 or ny < 0 or nx >= H or ny >= W:
            continue
        if grid[nx][ny] == "#":
            continue
        if dist[nx][ny] > d + 1:
            dist[nx][ny] = d + 1
            node.append((nx, ny))


ans = inf
for x, y in memo:
    d = min(x, y, H - x - 1, W - y - 1)
    ans = min(ans, 1 + (d + K - 1) // K)
print(ans)
### BUGGY CODE ###

n = int(input())
listN = [i+1 for i in range(n)]
listM = [j+2 for j in range(n-1)]
listM.append(1)
ans = 0
for k in range(n-1):
    ans += listN[k]%listM[k]
print(ans)


### FIXED CODE ###

n = int(input())
print(((n-1)*n)//2)
### BUGGY CODE ###

from bisect import*
def main():
    root=[[],[]]
    def search_higher(key):
        ptr=root
        ret=None
        while ptr[1]:
            i=bisect(ptr[0],key)
            if i!=len(ptr[0]):ret=ptr[0][i]
            ptr=ptr[1][i]
        i=bisect(ptr[0],key)
        if i!=len(ptr[0]):ret=ptr[0][i]
        return ret
    def search_lower(key):
        ptr=root
        ret=None
        while ptr[1]:
            i=bisect_left(ptr[0],key)
            if i!=0:ret=ptr[0][i-1]
            ptr=ptr[1][i]
        i=bisect_left(ptr[0],key)
        if i!=0:ret=ptr[0][i-1]
        return ret
    def insert_rec(ptr,key):
        b_size=1536
        if not ptr[1]:
            insort(ptr[0],key)
            if len(ptr[0])==b_size*2-1:
                ret=[ptr[0][:b_size],[]]
                ptr[0]=ptr[0][b_size:]
                return ret
        else:
            i=bisect(ptr[0],key)
            tmp=insert_rec(ptr[1][i],key)
            if tmp:
                ptr[0].insert(i,tmp[0].pop())
                ptr[1].insert(i,tmp)
                if len(ptr[1])==b_size*2:
                    ret=[ptr[0][:b_size],ptr[1][:b_size]]
                    ptr[0],ptr[1]=ptr[0][b_size:],ptr[1][b_size:]
                    return ret
    def insert(key):
        tmp=insert_rec(root,key)
        if tmp:root[0],root[1]=[tmp[0].pop()],[tmp,root]
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    insert(0)
    insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(search_higher(v)-v)*(v-search_lower(v))*i
        insert(v)
    print(c)
main()

### FIXED CODE ###

root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)
### BUGGY CODE ###

num = input()
l = []
for i in range(0,int(num)):
    l.append(input())

cnt = []
l_t = list(set(l))
for item in l_t:
    cnt.append(l.count(item))

num_dict = dict(zip(l_t,cnt))
max_v = max(num_dict.values())

keys = []

for word, num in num_dict.items():
    if num == max_v:
        keys.append(word)

for i in sorted(keys):
    print(i)

### FIXED CODE ###

from collections import Counter
N = int(input())
S = Counter(input() for _ in range(N))
m = max(S.values())
for v in sorted(k for k, v in S.items() if v == m):
	print(v)
### BUGGY CODE ###

import scipy.misc as scm

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

a = sorted(a, reverse=True)

comb = -1
for i in range(n-1):
    if scm.comb(a[i], int(a[i]/2)) <= comb:
        break
    else:
        r_list = a[i+1:]
        tmp_c = -1
        for r in r_list:
            c = scm.comb(a[i], r)
            if tmp_c < c:
                tmp_c = c
                tmp_r = r
        if tmp_c > comb:
            a_i = a[i]
            a_j = tmp_r
            comb = tmp_c
print(a_i, a_j)


### FIXED CODE ###

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

a = sorted(a, reverse=True)

comb = -1
a_i = a[0]
if a_i % 2 == 0:
    mid = int(a_i/2)
    dif = 10**9
    for i in range(1, n):
        if dif > abs(a[i]-mid):
            dif = abs(a[i]-mid)
            a_j = a[i]
else:
    mid = int(a_i/2)
    dif = 10**9
    for i in range(1, n):
        if a[i] > mid:
            if dif > abs(a[i]-mid-1):
                dif = abs(a[i]-mid-1)
                a_j = a[i]
        else:
            if dif > abs(a[i]-mid):
                dif = abs(a[i]-mid)
                a_j = a[i]

print(a_i, a_j)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

ps = [ list(input().split()) for _ in range(m) ]

ac_list = []
wa_count_list = [0]*n
wa_count = 0
ac_count = 0
for i in range(m):
    q = int(ps[i][0])
    if q in ac_list:
        pass
    else:
        if ps[i][1] == "AC":
            ac_count += 1
            ac_list.append(int(ps[i][0]))
            wa_count += wa_count_list[q-1]
        else:
            wa_count_list[q-1] += 1

print(ac_count,wa_count)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

ps = [ list(input().split()) for _ in range(m) ]

ac_count_list = [0]*n
wa_count_list = [0]*n
wa_count = 0

for i in range(m):
    q = int(ps[i][0])
    if ps[i][1] == "AC":
        if ac_count_list[q-1] == 0:
            ac_count_list[q-1] = 1
            wa_count += wa_count_list[q-1]
        else:
            pass
    else:
        if ac_count_list[q-1]==0:
            wa_count_list[q-1] += 1

print(sum(ac_count_list),wa_count)
### BUGGY CODE ###

import bisect
#input
n = int(input())
list1 = list(map(int,input().split()))
list1.sort()

cout = 0 #最終的な三角形の個数

for i in range(n-2): #リストから三角形が作れなくなるまでループ
	o = list1[i] #1辺を確定、そのままリストから消去
	for j in range(i+1,n-1): #残りの二辺のループ(iで使っている次の値から)
		p = list1[j] #２辺目を確定

		b = o+p -1 #昇順にソートしてあるので、c<a+b条件のみ計算

		d = bisect.bisect_right(list1[j+1:],b) #３辺目を確定
		
		cout += d

print(cout)

### FIXED CODE ###

import bisect
import copy

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

cout = 0
m,k = 0,0

for i in range(n-2):
	o = list1.pop(0)
	for j in range(n-i-1):
		p = list1[j]

		a = abs(o-p) +1
		b = o+p -1 #<= ではなく<条件に揃える

		d = bisect.bisect_right(list1[j+1:],b)
		
		cout += d

print(cout)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

B = [0]
[B.append(B[i]+A[i]) for i in range(N)]
B.sort()

ans = 0
for i in range(N):
    for j in range(i+1,N+1):
        if B[i] == B[j]:
            ans += 1
        else:
            break

print(ans)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]

B = {}
B[0] = 1

s = 0
ans = 0

for a in A:
    s += a
    ans += B.get(s,0)
    B[s] = B.get(s,0)+1

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

import sys


n = int(input())
xyh = []
for i in range(n):
    xyh.append(list(map(int, input().split())))

for cx in range(0, 101):
    for cy in range(0, 101):
        for H in range(max(1, xyh[0][2] - 201),
                       max(2, xyh[0][2] + 201)):
            is_valid = True
            for i in range(n):
                x, y, h = xyh[i]
                if max(H - abs(x - cx) - abs(y - cy), 0) != h:
                    is_valid = False
                    break
            if is_valid is True:
                print('{} {} {}'.format(cx, cy, H))
                sys.exit()


### FIXED CODE ###

import sys


n = int(input())
xyh = []
for i in range(n):
    xyh.append(list(map(int, input().split())))
    if xyh[-1][2] >= 1:
        G = xyh[-1]

for cx in range(0, 101):
    for cy in range(0, 101):
        hs = []
        x, y, h = G
        H = h + abs(x - cx) + abs(y - cy)
        H = max(H, 0)
        invalid = False
        for i in range(n):
            x, y, h = xyh[i]
            hh = H - abs(x - cx) - abs(y - cy)
            hh = max(hh, 0)
            if hh != h:
                invalid = True
                break
        if invalid is False:
            print("{} {} {}".format(cx, cy, H))
            sys.exit()
### BUGGY CODE ###

x = int(input())
res = 0

for i in range(x):
  num = i * i
  while num <= x:
    res = max(res, num)
    num *= i

print(res)

### FIXED CODE ###

x = int(input())
res = 1

for i in range(2, x):
  num = i * i
  while num <= x:
    res = max(res, num)
    num *= i
    
print(res)
### BUGGY CODE ###

a, b, x = map(int, input().split())
cnt = 0
for i in range(a, b + 1):
    if i % x == 0:
        cnt += 1
print(cnt)

### FIXED CODE ###

a, b, x = map(int, input().split())
if a % x == 0:
    print(b // x - a // x + 1)
else:
    print(b // x - a // x)
### BUGGY CODE ###

import operator
from functools import reduce

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

    ans = reduce(operator.mul, A, 1)
    
    if ans > 10 ** 18:
        print("-1")
    else:
        print(ans)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import operator
from functools import reduce

def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 1
    if 0 in A:
        print("0")
        exit()
    
    for i in A:
        ans *= i
        if ans > 10 ** 18:
            print(-1)
            exit()

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

import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

ans = 1
n = int(input())
arr = list(map(int , input().split()))
for i in range(n):
	ans*=arr[i]
if ans > 10**18:
	print(-1)
else:
	print(ans)



### FIXED CODE ###

ans = 1
n = int(input())
arr = sorted(list(map(int , input().split())))
f  = 1
for i in range(n):
	ans*=arr[i]
	#print(ans)
	if ans > 10**18:
		f = 0
		break
#print(ans)
if f: print(ans)
else: print(-1)
### BUGGY CODE ###

from collections import deque

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

for i in range(n):
    print(a.count(i+1))
    if a.count(i+1)!=0:
        while len(a)!=0 and a[0]==i+1:
            a.popleft()

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]*n

for i in a:
    b[i-1]+=1

[print(i) for i in b]
### BUGGY CODE ###

def main():
    n = int(input())
    *a, = map(int, input().split())
    o = float("inf")
    for i in range(1, n):
        l, r = sum(a[:i]), sum(a[i:])
        tmp = max(l, r) - min(l, r)
        o = tmp if tmp<o else o
    print(o)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    *a, = map(int, input().split())
    cs = [a[0]]*n
    for i in range(1, n):
        cs[i] = a[i]+cs[i-1]
    o = float("inf")
    for i in range(n):
        l, r = cs[i], cs[-1]-cs[i]
        tmp = max(l, r) - min(l, r)
        o = tmp if tmp<o else o
    print(o)

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

import math
K = int(input())
ans = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
            ans += math.gcd(i+1,math.gcd(j+1,k+1))
print(ans)

### FIXED CODE ###

from math import gcd
K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += gcd(gcd(i,j),k)
print(ans)
### BUGGY CODE ###

class SegmentTree():
    # リストSの部分リストからなる集合を葉とするセグメント木
    def __init__(self, S, n):
        self.size = n
        self.array = [set()] * (2**(self.size + 1) - 1)
        for i, c in enumerate(S):
            self.array[i + 2**self.size - 1] = {c}
        for i in range(2**self.size - 1)[::-1]:
            self.array[i] = self.array[2 * i + 1] | self.array[2 * i + 2]

    def subquery(self, l, r, k, i, j):
        # 区間[i,j)の中で区間[l,r)の文字列の集合を返す
        if j <= l or r <= i:
            return set()
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_set = self.subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_set = self.subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return l_set | r_set

    def query(self, l, r):
        # [l,r)に含まれる文字の種類数
        return len(self.subquery(l, r, 0, 0, 2**self.size))

    def update(self, i, c):
        # 配列のi番目をcに更新する
        tmp = i + 2**self.size - 1
        self.array[tmp] = {c}
        while tmp > 0:
            tmp = (tmp - 1) // 2
            self.array[tmp] = self.array[2 * tmp + 1] | self.array[2 * tmp + 2]


n = int(input())
S = list(input())
S = [ord(s) for s in S]
segtree = SegmentTree(S, 19)
for _ in range(int(input())):
    t, i, c = input().split()
    if t == '1':
        segtree.update(int(i)-1, ord(c))
    if t == '2':
        print(segtree.query(int(i)-1, int(c)))


### FIXED CODE ###

import sys
input = sys.stdin.readline


class SegmentTree():
    def __init__(self, S):
        self.size = 19
        self.array = [set()] * (2**(self.size + 1) - 1)
        for i, c in enumerate(S):
            self.array[i + 2**self.size - 1] = {c}
        for i in range(2**self.size - 1)[::-1]:
            self.array[i] = self.array[2 * i + 1] | self.array[2 * i + 2]

    def subquery(self, l, r, k, i, j):
        # 区間[i,j)の中で区間[l,r)の文字列の集合を返す
        if j <= l or r <= i:
            return set()
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_set = self.subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_set = self.subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return l_set | r_set

    def query(self, l, r):
        # [l,r)に含まれる文字の種類数
        return len(self.subquery(l, r, 0, 0, 2**self.size))

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = {c}
        while tmp > 0:
            tmp = (tmp - 1) // 2
            self.array[tmp] = self.array[2 * tmp + 1] | self.array[2 * tmp + 2]


def main():
    N = int(input())
    S = [ord(_) - 97 for _ in list(input())]
    Q = int(input())
    tree = SegmentTree(S)
    for q in range(Q):
        t, i, c = input().split()
        if t == '1':
            i = int(i) - 1
            tree.update(i, ord(c) - 97)
        else:
            l, r = int(i) - 1, int(c)
            print(tree.query(l, r))


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

def calc_length(s: str, l1: int, l2: int, n: int) -> int:
  max_len = min([l2 - l1, n - l2])
  for i in range(1, max_len):
    if s[l1 + i] != s[l2 + i]:
      return i
  return max_len

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

longest = 0
for l1 in range(n - 2, -1, -1):
  for l2 in range(l1 + longest + 1, n):
    if s[l1] == s[l2]:
      length = calc_length(s, l1, l2, n)
      if length > longest:
        longest = length

print(longest)

### FIXED CODE ###

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

l1 = l2 = length = 0

while l2 + length < n:
  if s[l1 : l2] in s[l2:]:
    length = l2 - l1
    l2 += 1
  else:
    l1 += 1
    l2 = l1 + length + 1

print(length)
### BUGGY CODE ###

from scipy.sparse import*
i=lambda:tuple(map(int,input().split()))
f=csgraph.bellman_ford
n,m,l=i()
d=eval('[0]*-~n,'*-~n)
exec('a,b,c=i();d[a][b]=c;'*m)
d=f(f(d,0)<=l)
d[d>n]=0
for _ in'_'*i()[0]:print(int(d[i()])-1)

### FIXED CODE ###

from scipy.sparse import*
s=csgraph.floyd_warshall
n,m,l,*t=map(int,open(0).read().split())
d=eval('[9e9]*-~n,'*-~n)
for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=d[b][a]=c
d=s(d)
d[d>l]=9e9
d[d<=l]=1
d=s(d)
d[d>9e9]=9e9
for s,t in zip(*[iter(t[m*3+1:])]*2):print(int(d[s,t]%9e9-1))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(99999999)

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

r = 0

for i in range(a, b+1):
    if i % x ==0:
        r += 1

print(r)


### FIXED CODE ###

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

r = b // x - (a-1) // x

print(r)
### BUGGY CODE ###

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def lm(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def gm(a, b):
    return a * b // lm(a, b)


def Prim(N):
    P = []
    M = int(N ** 0.5) + 10
    F = [False, False] + [True] * M
    for n in range(2, M):
        if not F[n]:
            continue
        P.append(n)
        for i in range(n, len(F), n):
            F[i] = False
    
    return P
 

def ps(a, P):
    d = {}
    for p in P:
        while a % p == 0:
            d[p] = d.setdefault(p, 0) + 1
            a //= p
        
        if a == 1:
            break
    
    if a != 1:
        d[a] = d.setdefault(a, 0) + 1
    return d


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()
    P = Prim(max(A))
    DA = [ps(a, P) for a in A]
    keys = set()
    for d in DA:
        keys.update(d.keys())

    D = {}
    res = 0
    for d in DA:
        b = 1
        for i in keys:
            v = d.setdefault(i, 0)
            r = D.setdefault(i, 0)
            if v > r:
                D[i] = v
                res = res * (i ** (v - r)) % mod
            else:
                b = b * (i ** (r - v)) % mod
        
        res = (res + b) % mod

    print(res)


if __name__ == "__main__":
    main()



### FIXED CODE ###

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def g(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()

    B = 1
    for a in A:
        B *= a // g(B, a)
    
    print(sum(B // a for a in A) % mod)


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

S = input()
T = input()
dp = [[0 for j in range(len(T)+1)] for i in range(len(S)+1)]

for i in range(len(S)) :
    for j in range(len(T)) :
        if S[i] == T[j] :
            dp[i+1][j+1] = dp[i][j] + 1
        else :
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

ans = ""

ind_x = len(T)
ind_y = len(S)

while ind_x * ind_y :
    if S[ind_y-1] == T[ind_x-1] :
        ans = S[ind_y-1] + ans
        ind_x -= 1
        ind_y -= 1
    elif dp[ind_y][ind_x] == dp[ind_y-1][ind_x] :
        ind_y -= 1
    else :
        ind_x -= 1
    

print(ans)


### FIXED CODE ###

s = input()
t = input()

H = len(s)
W = len(t)
dp = [[0 for x in range(W+1)] for y in range(H+1)]

for y in range(H) :
    for x in range(W) :
        if s[y] == t[x] :
            dp[y+1][x+1] = dp[y][x]+1
        else :
            dp[y+1][x+1] = max(dp[y+1][x], dp[y][x+1])

ans = ""

while (H > 0) and (W > 0) :
    if dp[H][W] == dp[H-1][W] :
        H -= 1
    elif dp[H][W] == dp[H][W-1] :
        W -= 1
    else :
        H -= 1
        W -= 1
        ans = s[H] + ans

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

N = int(input())
ans = 0
n = 1
while 1:
    if (N-n)%n == 0:
        m = (N-n)//n
        if m <= n: break
        ans += m
    n += 1
print(ans)

### FIXED CODE ###

N = int(input())
ans = 0

n = 1
while n*n < N:
    if N%n==0 and n < N//n-1:
        ans += N//n-1
    n += 1
print(ans)