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

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

a.sort()
a_set = set(a)
for i in range(n-1):
    if a[i] == a[i + 1]:
        if a[i] in a_set:
            a_set.remove(a[i])

dp = [True for _ in range(max(a)+1)]
y = -1
for x in a:
    if x == y:
        continue
    y = 2*x
    while y <= max(a):
        dp[y] = False
        y += x

ans = 0
for x in list(a_set):
    ans += 1 if dp[x] else 0

print(ans)


### FIXED CODE ###

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

a.sort()
a_set = set(a)
for i in range(n-1):
    if a[i] == a[i + 1]:
        if a[i] in a_set:
            a_set.remove(a[i])

ma = max(a)

dp = [True for _ in range(ma + 1)]
ans = 0
y = -1
for x in a:
    if x == y:
        continue
    y = x

    if x in a_set:
        ans += 1 if dp[x] else 0

    while y <= ma:
        dp[y] = False
        y += x

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

import math
import collections
def calc_combi2(n):
    if n<=1:
        return 0
    return math.factorial(n)/(math.factorial(n-2)*math.factorial(2))
n=int(input())
data=list(map(int,input().split()))
data_cnt=collections.Counter(data)
count=0
for i in data_cnt.values():
    count+=calc_combi2(i)
for i in data:
    ans=count+(calc_combi2(data_cnt[i]-1)-calc_combi2(data_cnt[i]))
    print(int(ans))

### FIXED CODE ###

import math
import collections
def calc_combi2(n):
    if n<=1:
        return 0
    return math.factorial(n)/(math.factorial(n-2)*math.factorial(2))
n=int(input())
data=list(map(int,input().split()))
data_cnt=collections.Counter(data)
count=0
for i in data_cnt.values():
    count+=calc_combi2(i)
for i in data:
    ans=count-data_cnt[i]+1
    print(int(ans))
### BUGGY CODE ###

import numpy as np
import itertools
N, M=map(int, input().split())
a =[]
c = []
for i in range(2*M):
  if i%2 == 0:
    temp,_=map(int, input().split()) 
    a.append(temp)
  else:
    temp=list(map(int, input().split()))
    c.append(temp)
a = np.array(a) 
mini = -1

for n in range(M):
    for l in list(itertools.combinations(range(M),n+1)):
        temp = [c[nn] for nn in l]
        temp = set(itertools.chain.from_iterable(temp))
        if len(temp) == N:
            cost = sum(a[[np.array(l)]])
            if mini == -1 or mini > cost:
                mini = cost

print(mini)  


### FIXED CODE ###

N, M = map(int, input().split())
Inf = 10**8
Dp = [Inf]*(2**N)
Dp[0] = 0

for i in range(M): #カギiで
    a,_=map(int, input().split())
    c = list(map(int, input().split()))
    d = sum((1<<p-1) for p in c) #iで開けられる宝箱の2bit表記
    for j in range(2**N):
        ope = j|d
        Dp[ope] = min(Dp[ope], Dp[j] + a)

if Dp[-1] == Inf:
    print(-1)
else:
    print(Dp[-1])
### BUGGY CODE ###

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

dp=[[0]*(n+1) for _ in range(s+1)]
for i in range(n+1):
    dp[0][i]=1
ans=0

# i indicade low , c indicade column
for i,w in enumerate(a):
    for c in range(s+1):
        dp[c][i]+=dp[c][i-1]
    for c in range(s-w+1):
        dp[c+w][i]+=dp[c][i-1]
    ans+=dp[-1][i]
    ans%=998244353

print(ans)

### FIXED CODE ###

import numpy as np

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

dp=[np.zeros(s+1,dtype=np.int64) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0]=1
ans=0

for i,w in enumerate(a):
    dp[i]+=dp[i-1]
    dp[i][w:]+=dp[i-1][:-w]
    dp[i]%=998244353
    ans+=dp[i][-1]
    ans%=998244353

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

import collections

N, K = map(int, input().split())
A = map(int, input().split())
counter = 0
collection = collections.Counter(A)
k = len(collection)
if k > K:
  change_n = k - K
  for i in range(change_n):
    min_k = collection.most_common()[-1-i][1]
    counter += min_k

print(counter)

### FIXED CODE ###

N, K = map(int, input().split())
A = map(int, input().split())
counter = 0
dic = {}

for a in A:
  if a in dic.keys():
    dic[a] += 1
  else:
    dic[a] = 1

k = len(dic)
v = sorted(dic.values())
if k > K:
  change_n = k -K
  for i in range(change_n):
    min_k = v[i]
    counter += min_k

print(counter)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
ans = [K]*N
def minus(n):
    return n-1
for i in range(1, Q+1):
    ans = list(map(minus, ans))
    ans[A[i-1]-1] += 1    
for k in ans:
    if k <= 0:
        print('No')
    else:
         print('Yes')

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
ans = [K-Q]*N
for i in range(1,Q+1):
    ans[A[i-1]-1] += 1    
for k in ans:
    if k <= 0:
        print('No')
    else:
         print('Yes')
### BUGGY CODE ###

from collections import defaultdict
MAX_N = 10 ** 3 + 10
MAX_M = 2 * (10 ** 3) + 1
INF = 10 ** 13

def bfs(graph, N, M):
    que = []
    que.append([0, 0])
    visited = [-INF for x in range(MAX_N)]
    update_cnt = [0 for x in range(MAX_N)]
    result = -INF
    while (len(que) > 0):
        now = que[0]
        que.pop(0)

        pos = now[0]
        cost = now[1]

        if (visited[pos] != -INF):
            if (visited[pos] >= cost):
                continue
            if (update_cnt[pos] >= MAX_N):
                continue
            visited[pos] = cost
            update_cnt[pos] += 1
        else:
            visited[pos] = cost
            update_cnt[pos] += 1

        if (pos == N - 1):
            result = max(result, cost)

        for val in graph[pos]:
            nxt = val[0]
            nxt_cost = val[1]
            if (cost + nxt_cost > visited[nxt]):
                que.append([nxt, nxt_cost + cost])

    if (update_cnt[N - 1] >= MAX_N):
        return (0, False)
    return (result, True)


if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = defaultdict(list)
    for x in range(M):
        a,b,c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    res,ok = bfs(graph, N, M)
    if (not ok):
        print ('inf')
    else:
        print (res)


### FIXED CODE ###


MAX_N = 10 ** 3 + 10
MAX_M = 2 * (10 ** 3) + 1
INF = 10 ** 13

def bfs(graph, N, M):
    que = []
    que.append([0, 0])
    visited = [-INF for x in range(MAX_N)]
    update_cnt = [0 for x in range(MAX_N)]
    result = -INF
    while (len(que) > 0):
        now = que[0]
        que.pop(0)

        pos = now[0]
        cost = now[1]
        if (visited[pos] > cost):
            continue
        for val in graph[pos]:
            nxt = val[0]
            nxt_cost = val[1]

            if (cost + nxt_cost > visited[nxt] and update_cnt[nxt] < MAX_M):
                visited[nxt] = cost + nxt_cost
                update_cnt[nxt] += 1
                que.append([nxt, nxt_cost + cost])

    if (update_cnt[N - 1] >= MAX_N):
        return (0, False)
    return (visited[N - 1], True)


if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = [[] for x in range(MAX_N)]
    for x in range(M):
        a,b,c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    res,ok = bfs(graph, N, M)
    if (not ok):
        print ('inf')
    else:
        print (res)
### BUGGY CODE ###

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


def solve(N: int, D: int, A: int, X: "List[int]", H: "List[int]"):
    M = sorted([(X[i], H[i]) for i in range(N)])
    DD = 2*D
    result = 0
    next = 0
    while next <= N-1:
        hasNonZero = False
        breaken = False
        left = M[next]
        attackCount = math.ceil(left[1]/A)
        damage = attackCount*A
        result += attackCount
        # print(f"max X:{left[0]+DD}")
        for i in range(next, N):
            if M[i][0] <= left[0]+DD:
                M[i] = (M[i][0], max(0, M[i][1]-damage))
                if not hasNonZero and M[i][1] != 0:
                    hasNonZero = True
                    breaken = True
                    next = i
            else:
                if not hasNonZero:
                    next = i
                breaken = True
                break
        if not breaken:
            next = N
        # print(f"next:{next}")
        # print(M)
    print(result)
    return


# Generated by 1.1.6 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()
    N = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    X = [int()] * (N)  # type: "List[int]"
    H = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        X[i] = int(next(tokens))
        H[i] = int(next(tokens))
    solve(N, D, A, X, H)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math
from collections import deque


def solve(N: int, D: int, A: int, X: "List[int]", H: "List[int]"):
    M = sorted([(X[i], H[i]) for i in range(N)])
    DD = 2*D
    result = 0
    revert = deque()
    currentDamage = 0
    for m in M:
        while len(revert) > 0 and revert[0][0] < m[0]:
            currentDamage -= revert[0][1]
            revert.popleft()
        nextDamage = max(0, m[1] - currentDamage)
        needAttack = math.ceil(nextDamage/A)
        currentDamage += needAttack * A
        result += needAttack
        if needAttack > 0:
            revert.append((m[0]+2*D, needAttack*A))
    print(result)
    return


# Generated by 1.1.6 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()
    N = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    X = [int()] * (N)  # type: "List[int]"
    H = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        X[i] = int(next(tokens))
        H[i] = int(next(tokens))
    solve(N, D, A, X, H)


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

def p_l():
    import sys
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    *a, = map(int, input().split())
    # dp[i][j]は区間[i,j]が残っているときの最大化
    dp = [[-1] * n for _ in range(n)]

    def dfs(l, r):
        if dp[l][r] != -1:
            return dp[l][r]
        if l == r:
            dp[l][r] = a[l]
            return a[l]
        dp[l][r] = max(a[l] - dfs(l + 1, r), a[r] - dfs(l, r - 1))
        return dp[l][r]

    dfs(0, n - 1)
    print(dp[0][n - 1])


if __name__ == '__main__':
    p_l()


### FIXED CODE ###

def p_l_2():
    n = int(input())
    *a, = map(int, input().split())
    # dp[i][j]は区間[i,j]が残っているときの最大化
    dp = [[-1] * n for _ in range(n)]

    for i in range(n):
        for l in range(n - i):
            r = l + i
            if l == r:
                dp[l][r] = a[l]
            else:
                dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1])
    print(dp[0][n - 1])


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

N = int(input())
ABCs = [
  sorted(map(int, input().split()))
  for _ in range(3)
]

def table(As, Bs):
  ib = 0
  result = []
  for a in As:
    while ib < N and Bs[ib] <= a:
      ib += 1
    result.append(ib)
  return result

def table2(Bs, Cs):
  ic = 0
  result = []
  for b in Bs:
    while ic < N and Cs[ic] <= b:
      ic += 1
    result.append(N-ic)
  return result

def f(ABCs):
  AB = table(ABCs[0], ABCs[1])
  BC = table2(ABCs[1], ABCs[2])
  
  def Cs():
    for i, bmin in enumerate(AB):
      yield sum(BC[bmin:])
  
  return sum(Cs())
  
print(f(ABCs))

### FIXED CODE ###

N = int(input())
As, Bs, Cs = [
  sorted(map(int, input().split()))
  for _ in range(3)
]

from bisect import *

def sums():
  for b in Bs:
  	yield bisect_left(As, b) * (N - bisect_right(Cs, b))

print(sum(sums()))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
s=input()
move=[tuple(input().split()) for i in range(Q)]
inf=float('inf')
alive=[inf,-1*inf]
dead=[-1*inf,inf]
def check(i):
    now=i
    for j in range(Q):
        if move[j][0]==s[now]:
            if move[j][1]=='L':
                now-=1
            elif move[j][1]=='R':
                now+=1
        if now<0:
            return 'left'
        if now>N-1:
            return 'right'
    return 'alive'
from collections import deque
search=deque([(1,2)])
while len(search)>0:
    now=search.popleft()
    idx=now[0]*N//now[1]
    res=check(idx)
    if res=='alive':
        if alive[0]>alive[1]:
            alive=[idx,idx]
            search.append((2*now[0]-1,2*now[1]))
            search.append((2*now[0]+1,2*now[1]))
        elif idx<alive[0]:
            alive[0]=idx
            search.append((2*now[0]-1,2*now[1]))
        elif idx>alive[1]:
            alive[1]=idx
            search.append((2*now[0]+1,2*now[1]))
    elif res=='left':
        if idx>dead[0]:
            dead[0]=idx
            search.append((2*now[0]+1,2*now[1]))
    elif res=='right':
        if idx<dead[1]:
            dead[1]=idx
            search.append((2*now[0]-1,2*now[1]))
if alive[0]>alive[1]:
    print(0)
else:
    print(alive[1]-alive[0]+1)

### FIXED CODE ###

import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
s=input()
move=[input().split() for i in range(Q)]
inf=float('inf')
alive=[inf,-1*inf]
dead=[-1*inf,inf]
def check(i):
    now=i
    for m in move:
        if m[0]==s[now]:
            if m[1]=='L':
                now-=1
            elif m[1]=='R':
                now+=1
        if now<0:
            return 'left'
        if now>N-1:
            return 'right'
    return 'alive'
def search(now,alive,dead):
    if dead[0]+1==alive[0] and dead[1]-1==alive[1] or dead[0]+1==dead[1]:
        return alive,dead
    idx=now[0]*N//now[1]
    res=check(idx)
    if res=='alive':
        if alive[0]>alive[1]:
            alive=[idx,idx]
            alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
            alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
        elif idx<alive[0]:
            alive[0]=idx
            if alive[0]-1!=dead[0]:
                alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
        elif idx>alive[1]:
            alive[1]=idx
            if alive[1]+1!=dead[1]:
                alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
        elif idx==0 or idx==N-1:
            return alive,dead
    elif res=='left':
        if idx>dead[0]:
            dead[0]=idx
            if dead[0]+1!=alive[0]:
                alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
    elif res=='right':
        if idx<dead[1]:
            dead[1]=idx
            if dead[1]-1!=alive[1]:
                alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
    return alive,dead
alive,dead=search((1,2),alive,dead)
if alive[0]>alive[1]:
    print(0)
else:
    print(alive[1]-alive[0]+1)
### BUGGY CODE ###

from collections import Counter


def check(s1, s2):
    s1_cnt = Counter(s1)
    s2_cnt = Counter(s2)
    if s1_cnt == s2_cnt:
        return 1
    else:
        return 0


N = int(input())

S = []
for _ in range(N):
    S.append(input())

ans = 0
for i in range(N):
    for j in range(i+1, N):
       ans += check(S[i], S[j])

print(ans)


### FIXED CODE ###

import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
ans_dict = {}

for _ in range(n):
    s = list(input())
    s.sort()
    s = ''.join(s)
    try:
        ans_dict[s] += 1
    except:
        ans_dict[s] = 1

ans = 0
for key in ans_dict:
    if ans_dict[key] >= 2:
        ans += combinations_count(ans_dict[key], 2)
print(ans)
### BUGGY CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**7)
    n, q = map(int, input().split(' '))
    visit = [0 for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]

    def add_p(num):
        if visit[num] == 1:
            return 0
        visit[num] = 1
        for i in dic[num]:
            if visit[i] == 0:
                point[i] += point[num]
                add_p(i)
        return 0

    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    add_p(0)
    print(*point)

main()

### FIXED CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    from collections import deque
    sys.setrecursionlimit(10**7)

    visit = [True for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = deque()
    next_visit.append(0)
    visit[0] = False
    counter = 1
    while counter < n:
        t = next_visit.pop()
        for s in dic[t]:
            if visit[s]:
                point[s] += point[t]
                visit[s] = False
                counter += 1
                next_visit.append(s)
    print(*point)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
from itertools import accumulate

s_in = lambda: stdin.readline()[:-1] # s = s_in()
d_in = lambda: int(stdin.readline()) # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split())) # List = ds_in()

MOD = 10**9 + 7

N = d_in()
A_list = ds_in()

def factorial(N):
    val = 1
    for i in range(1, N+1):
        val = (val * i) % MOD
    return val

def recursive_square(n, m, p):
    """ n**p (mod m) """
    if p == 0:
        return 1 % m
    if p % 2 == 0:
        root = recursive_square(n, m, p//2) % m 
        return (root ** 2) % m
    else:
        return ((n % m) * recursive_square(n, m, p-1)) % m


N_factorial = factorial(N)

Coefs = []
for i in range(1, N+1):
    Coefs.append((N_factorial * recursive_square(i, MOD, MOD-2)) % MOD)

def CumSum(x):
    c = []
    last = 0
    for i in range(len(x)):
        last = (last + x[i]) % MOD
        c.append(last)
    return c
        
Cum_Coefs = CumSum(Coefs)

if N == 1:
    print(A_list[0])
else: 
    ans = 0
    for i in range(N):
        ans = (ans + A_list[i] * (Cum_Coefs[i] + Cum_Coefs[N-i-1] - Cum_Coefs[0])) % MOD 
    print(ans)





### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
from itertools import accumulate

s_in = lambda: stdin.readline()[:-1] # s = s_in()
d_in = lambda: int(stdin.readline()) # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split())) # List = ds_in()

MOD = 10**9 + 7

N = d_in()
A_list = ds_in()

def factorial(N):
    val = 1
    for i in range(1, N+1):
        val = (val * i) % MOD
    return val

def recursive_square(n, m, p):
    """ n**p (mod m) """
    if p == 0:
        return 1 % m
    if p % 2 == 0:
        root = recursive_square(n, m, p//2) % m 
        return (root ** 2) % m
    else:
        return ((n % m) * recursive_square(n, m, p-1)) % m
        
def factorize(n):
    if n == 1:
        return [(1, 1)]
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n //= b
            e += 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

N_factorial = factorial(N)

Coefs = []
lastval = 0
Inv = dict()
for i in range(1, N+1):
    fac = factorize(i)
    temp = N_factorial
    for f in fac:
        if f[0] not in Inv.keys():
            Inv[f[0]] = recursive_square(f[0], MOD, MOD-2)
        for _ in range(f[1]):
            temp = (temp * Inv[f[0]]) % MOD
    lastval = (lastval + temp) % MOD
    Coefs.append(lastval)

if N == 1:
    print(A_list[0])
else: 
    ans = 0
    for i in range(N):
        ans = (ans + A_list[i] * (Coefs[i] + Coefs[N-i-1] - Coefs[0])) % MOD 
    print(ans)
### BUGGY CODE ###

N = int(input())
for i in range(1,3501):
    h = i
    for j in range(1,3501):
        n = j
        if (4*h*n-N*n-N*h) != 0:
            w = (N*h*n)/(4*h*n-N*n-N*h)
            if w.is_integer() is True and w > 1:
                print(h,n,int(w))
                exit()


### FIXED CODE ###

N = int(input())
for i in range(1,3501):
    h = i
    for j in range(1,3501):
        n = j
        wb = (4*h*n-N*n-N*h)
        if wb > 0:
            w = (N*h*n)/wb
            if w.is_integer() is True:
                print(h,n,int(w))
                exit()
### BUGGY CODE ###

N = int(input())
S = list(input())
ans = 0

for i in range(N):
    first_s = S[i]
    for j in range(i+1, N):
        if S[j] != first_s:
            second_s = S[j]
            for k in range(j+1, N):
                if (S[k] != first_s) and (S[k] != second_s):
                    if k == 2*j-i:
                        continue
                    ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())

r, g, b = 0, 0, 0
ans = 0
for i in range(N):
    if S[i] == 'R':
        r += 1
    elif S[i] == 'G':
        g += 1
    else:
        b += 1

ans += r*g*b

for i in range(N):
    for j in range(i+1, N):
        if 2*j-i < N:
            if (S[i] != S[j]) and (S[j] != S[2*j-i]) and (S[i] != S[2*j-i]):
                ans -= 1

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

n,k,q = map(int,input().split())
Ans = [int(input()) for i in range(q)]
for j in range(n):
	if k - q + Ans.count(j+1) > 0:
		print("Yes")
	else:
		print("No")

### FIXED CODE ###

n,k,q = map(int,input().split())
points = []
for i in range(n):
	points.append(k-q)
for i in range(q):
	points[int(input())-1]+=1
for i in range(n):
	if points[i]>0:
		print("Yes")
	else:
		print("No")
### BUGGY CODE ###

N, W = map(int, input().split())
dp = [0] * (W + 1)
for i in range(N):
    w, v = map(int, input().split())
    for wk in range(W, w - 1, -1):
        tv = dp[wk - w] + v
        if tv > dp[wk]:
            dp[wk] = tv



print(max(dp))


### FIXED CODE ###

def main():
    n, w = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(n)]

    dp = [0] * (w + 1)
    for wi, vi in wv:
        for sum_w in range(w, wi - 1, -1):
            v = dp[sum_w - wi] + vi
            if dp[sum_w] < v:
                dp[sum_w] = v

    print(dp[w])


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

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

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

count = [0] * len(set(A))
labels = set(A)
for val in A:
    for i, label in enumerate(labels):
        if label==val:
            count[i] += 1

ans = 0
diff = len(set(A)) - K
if diff > 0:
    count_sorted = sorted(count)
    for i in range(diff):
        ans += count_sorted[i]

print(ans)

### FIXED CODE ###

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

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

count = {}
for val in A:
    if val in count:
        count[val] += 1
    else:
        count[val] = 1

ans = 0
diff = len(set(A)) - K
if diff > 0:
    count_sorted = sorted(count.items(), key=lambda x:x[1])
    for k,v in count_sorted:
        ans += v
        diff -= 1
        if diff == 0:
            break

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

def s():
  from sys import stdin
  read=stdin.buffer.readline
  n=int(read())
  l=list(map(int,read().split()))
  f=l[0]
  mod=10**9+7
  def gcd(s,d):
    s,d=max(s,d),min(s,d)
    while  d:
      s,d=d,s%d
    return s
  if len(set(l))*2<=n:
    from itertools import groupby as gb
    sl,kl=[list(a) for a in zip(*[(q,len(list(w))) for q,w in gb(sorted(l))] )]
    for i in sl:
      f=i*f//gcd(i,f)
    ans=0
    for i,iy in enumerate(sl):
      ans+=(f//iy)*kl[i]%mod
    print(ans)
    exit()
  for i in l:
    f=i*f//gcd(i,f)
  ans=0
  for iu in l:
    ans+=(f//iu)%mod
    ans%=mod
  print(ans)
  
if __name__=="__main__":s()

### FIXED CODE ###

def s():
  from sys import stdin
  read=stdin.buffer.readline
  n=int(read())
  l=list(map(int,read().split()))
  f=l[0]
  mod=10**9+7
  def gcd(s,d):
    s,d=max(s,d),min(s,d)
    while  d:
      s,d=d,s%d
    return s
  for i in l:
    f=i*f//gcd(i,f)
  ans=0
  for iu in l:
    b,u,v=mod,1,0
    while b:
      t=iu//b;iu,b=b,iu%b;u-=t*v;u,v=v,u
    ans+=(f*u%mod)%mod
    ans%=mod
  print(ans)
  
if __name__=="__main__":s()