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

import sys
sys.setrecursionlimit(500000)
INF = -10000000001

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

a = int(n/2)

dpa = [[INF for j in range(a+1)] for i in range(n+1)]

def dp(x,y):
	ret = 0
	if 2*y-1 > x:
		ret = INF
	elif 2*y-1 == x:
		for i in range(0,x,2):
			ret+= l[i]
	elif y == 0:
		ret = 0
	else:
		if dpa[x][y] != INF:
			ret = dpa[x][y]
		else:
			ret = max(dp(x-2,y-1)+l[x-1],dp(x-1,y))
#			print(x,y,"->",x-2,y-1,x-1,y)
#	print(x,y,ret)
	dpa[x][y] = ret
	return ret

print(dp(n,a))

### FIXED CODE ###

from collections import defaultdict
INF = -1000000000000001

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

a = int(n/2)

dpa = defaultdict(lambda: -INF)
#dpa = [[0 for j in range(a+1)] for i in range(n+1)]

dpa[(0,0)] = 0
dpa[(1,0)] = 0
dpa[(1,1)] = l[0]
j = 1
for i in range(2,n+1):
	if i == j*2:
		dpa[(i,j)] = max(dpa[(i-2,j-1)]+l[i-1],dpa[(i-1,j)])
#		print(i,j,dpa[(i,j)])
	else:
		dpa[(i,j)] = max(dpa[(i-2,j-1)]+l[i-1],dpa[(i-1,j)])
#		print(i,j,dpa[(i,j)])
		if (i != n):
			j += 1
#			print(i,j,dpa[(i,j)])
#			print("   ",i-2,j-1,dpa[(i-2,j-1)],"")
			dpa[(i,j)] = dpa[(i-2,j-1)]+l[i-1]

#print(dpa)
print(dpa[n,a])
### BUGGY CODE ###

n = int(input())

ans = 0
input_list = []
for i in range(n):
    s = input()
    if s in input_list: continue
    input_list.append(s)
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())

ans = 0
input_list = []
for i in range(n): input_list.append(input())
for i in set(input_list):
    ans += 1
print(ans)
### BUGGY CODE ###

import math
number, jump =input().rstrip().split()
number = int(number)
jump = int(jump)
scaffolding = input().rstrip().split()
scaffolding = list(map(int, scaffolding))
res = [math.inf for i in range(number)]
res[0] =0 


for i in range(number):
    test = [math.inf for k in range(jump)]
    test[0] = 0
    for j in range(1,jump+1):
        if i-j < 0:break
        cost = abs(scaffolding[i]-scaffolding[i-j])
        test[j-1] = res[i-j] + cost
    
    res[i] = min(test)
    

print(res[number-1])

### FIXED CODE ###

import math
import sys
input = sys.stdin.readline
number, jump =input().rstrip().split()
number = int(number)
jump = int(jump)
scaffolding = input().rstrip().split()
scaffolding = list(map(int, scaffolding))
res = [0 for i in range(number)]
res[1] = abs(scaffolding[1]-scaffolding[0])
#test = [math.inf for k in range(jump)]
#test[0] = 0

for i in range(2, number):
    h=max(0,i-jump)
    res[i]=min(res[k]+abs(scaffolding[i]-scaffolding[k]) for k in range(h,i))   
    #res[i] = min(test)
    

print(res[number-1])
### BUGGY CODE ###

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


c = 0
a = 0

t = [0]*(n+1)

temp = []


for i in range(m):
    s = input().split()
    x = s[0]
    y = s[1]
    if x not in temp:
        if y == 'AC':
            a += 1
            c += t[int(x)]
            temp += [x]
        elif y == 'WA':
            t[int(x)] += 1
    elif len(temp) == n:
        break

print(a, c)


### FIXED CODE ###

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

a = [0] * (n+1)
b = [0] * (n+1)

c = 0

for i in [0]*(m):

    s = input().split()

    if a[int(s[0])] == 0:
        if s[1] == "AC":
            a[int(s[0])] = 1
            c += b[int(s[0])]
        else:
            b[int(s[0])] += 1

print(sum(a), c)
### BUGGY CODE ###

num_of_employee = int(input())
employeenos = list(map(int, input().split()))

bossenos = set(employeenos)
output = [0] * (len(employeenos) + 1)
for boss in bossenos:
    output[boss - 1] = employeenos.count(boss)

for _ in output:
    print(_)

### FIXED CODE ###

import collections

num_of_employee = int(input())
employeenos = list(map(int, input().split()))

c = collections.Counter(employeenos)
for i in range(1, num_of_employee + 1):
    print(c[i])
### BUGGY CODE ###

import math

def prime_judge(n):
    if n==1:
        return False
    elif n==2:
        return True
    elif n%2==0:
        return False
    else:
        sqrt_num=math.ceil(math.sqrt(n))+1
        for i in range(3,sqrt_num, 2):
            if n%i==0:
                return False
        return True

def prime_count(n):
    count=0
    for i in range(1,n+1):
        if prime_judge(i):
            count+=1
    print(count)

while 1:
    try:
        prime_count(int(input()))        
    except EOFError:
        break


### FIXED CODE ###

def prime_judge(n):
    if n==1:
        return False
    elif n==2:
        return True
    elif n%2==0:
        return False
    else:
        sqrt_num=int(n**0.5)+1
        for i in range(3,sqrt_num, 2):
            if n%i==0:
                return False
        return True

prime=[0]
for i in range(1,1000000):
    if prime_judge(i):
        prime.append(prime[-1]+1)
    else:
        prime.append(prime[-1])

while 1:
    try:
        print(prime[int(input())])     
    except:
        break
### BUGGY CODE ###

from itertools import product

N=int(input())
S=input()
t=["0","1","2","3","4","5","6","7","8","9"]

u=product(t,repeat=3)
ans=0
for com in u:
  flag=False
  x=com[0]
  y=com[1]
  z=com[2]
  for i in range(N):
    if S[i]==x:
      for j in range(i+1,N):
        if S[j]==y:
          tmp=S[j+1:]
          if z in tmp:
            flag=True
            break
      else:
        break
  if flag:
    ans+=1
print(ans)


### FIXED CODE ###

from itertools import product

N=int(input())
S=list(input())
t=["0","1","2","3","4","5","6","7","8","9"]

u=product(t,repeat=3)
ans=0
for com in u:
  x=com[0]
  y=com[1]
  z=com[2]
  
  if x in set(S):
    idx_x = S.index(x)
    tmp1 = S[idx_x+1:]
    if y in set(tmp1):
      idx_y = tmp1.index(y)
      tmp2 = tmp1[idx_y+1:]
      if z in set(tmp2):
        ans+=1
        continue
        
print(ans)
### BUGGY CODE ###

N = int(input())
x = [] * N
y = [] * N
for i in range(N):
    a, b = list(map(int, input().split()))
    x.append(a)
    y.append(b)
d = 0
for i in range(N):
    for j in range(i+1, N):
        w = abs(x[i] - x[j]) + abs(y[i] - y[j])
        if w > d:
            d = w
print(d)

### FIXED CODE ###

N = int(input())
x = [] * N
y = [] * N
for i in range(N):
    a, b = list(map(int, input().split()))
    x.append(a)
    y.append(b)
d = 0
ma = x[0] + y[0]
ima = 0
mi = x[0] + y[0]
imi = 0
for i in range(N):
    if x[i] + y[i] < mi:
        mi = x[i] + y[i]
        imi = i
    if x[i] + y[i] > ma:
        ma = x[i] + y[i]
        ima = i
d1 = abs(x[ima] - x[imi]) + abs(y[ima] - y[imi])
ma = - x[0] + y[0]
ima2 = 0
mi = - x[0] + y[0]
imi2 = 0
for i in range(N):
    if -x[i] + y[i] < mi:
        mi = -x[i] + y[i]
        imi2 = i
    if -x[i] + y[i] > ma:
        ma = -x[i] + y[i]
        ima2 = i
d2 = abs(x[ima2] - x[imi2]) + abs(y[ima2] - y[imi2])
if d1 > d2:
    print(d1)
else:
    print(d2)
### BUGGY CODE ###

a,b,n = map(int,input().split())
ans = -10**10
for i in range(1,n+1):
    t = (a*i)//b
    f = i//b
    s = t-a*f
    if ans > s:
        break
    else:
        ans = s

print(ans)


### FIXED CODE ###

a,b,n = map(int,input().split())
ans = 0
if n >= b:
    ans = (a*(b-1))//b
else:
    ans = (a*n)//b
print(ans)
### BUGGY CODE ###

# string
# a, b, c = input().split()
# str_list = list(input().split())

# number
# a, b, c = map(int, input().split())
# num_list = list(map(int, input().split()))

# lows
# str_list = [input() for _ in range(n)]

# many inputs
# num_list = []
# for i in range(n): num_list.append(list(map(int, input().split())))

from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

dx = [1,0,-1,0]
dy = [0,1,0,-1]

s = []
for i in range(h): s.append(list(input()))

inf = int(1e9)
dist = [[inf for j in range(w)] for i in range(h)]
dist[ch][cw] = 0

q = deque()
q.append([ch,cw])

while len(q) != 0:
    i, j = map(int, q.popleft())
    d = dist[i][j]
    
    for v in range(4):
        ni = i + dx[v]
        nj = j + dy[v]

        if ni < 0 or ni >= h or nj < 0 or nj >= w:
            continue
        
        if s[ni][nj] == "#":
            continue

        if dist[ni][nj] <= d:
            continue
        
        dist[ni][nj] = d
        q.appendleft([ni, nj])
    
    for ei in range(-2, 3):
        for ej in range(-2, 3):
            ni = i + ei
            nj = j + ej

            if ni < 0 or ni >= h or nj < 0 or nj >= w:
                continue
        
            if s[ni][nj] == "#":
                continue

            if dist[ni][nj] <= d+1:
                continue

            dist[ni][nj] = d+1
            q.append([ni, nj])

ans = dist[dh][dw]
if ans == inf:
    ans = -1
print(ans)

### FIXED CODE ###

# string
# a, b, c = input().split()
# str_list = list(input().split())

# number
# a, b, c = map(int, input().split())
# num_list = list(map(int, input().split()))

# lows
# str_list = [input() for _ in range(n)]

# many inputs
# num_list = []
# for i in range(n): num_list.append(list(map(int, input().split())))

from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

dx = [1,0,-1,0]
dy = [0,1,0,-1]

s = []
for i in range(h): s.append(list(input()))

inf = int(1e9)
dist = [[inf for j in range(w)] for i in range(h)]
dist[ch][cw] = 0

q = deque()
q.append([ch,cw])

while len(q) != 0:
    i, j = map(int, q.popleft())
    d = dist[i][j]
    
    for v in range(4):
        ni = i + dx[v]
        nj = j + dy[v]

        if ni < 0 or ni >= h or nj < 0 or nj >= w:
            continue
        
        if s[ni][nj] == "#":
            continue

        if dist[ni][nj] <= d:
            continue
        
        dist[ni][nj] = d
        q.appendleft([ni, nj])
    
    for ei in range(-2, 3):
        for ej in range(-2, 3):
            ni = i + ei
            nj = j + ej

            if ni < 0 or ni >= h or nj < 0 or nj >= w:
                continue
        
            if s[ni][nj] == "#":
                continue

            if dist[ni][nj] <= d+1:
                continue

            dist[ni][nj] = d+1
            q.append([ni, nj])

ans = dist[dh][dw]
if ans == inf:
    ans = -1
print(ans)
### BUGGY CODE ###

import sys
import numpy as np

def input():
	return sys.stdin.readline().rstrip()
def main():
	N = int(input())
	A = [int(input()) for _ in range(N)]
	for i in range(N):
		B = A[:]
		B.pop(i)
		print(max(B))
if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys
import copy
def input():
	return sys.stdin.readline().rstrip()
def main():
	N = int(input())
	A = [int(input()) for _ in range(N)]
	B = list(set(A))
	if (len(B) == 1) or (A.count(B[-1]) > 1):
		for i in range(N):
			print(B[-1])
	else :
		for i in range(N):
			if A[i] == B[-1]:
				print(B[-2])
			else:
				print(B[-1])
if __name__ == '__main__':
	main()
### BUGGY CODE ###

import collections
import math


def comb(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


input()
a = list(map(int, input().split()))
c = collections.Counter(a)

summ = sum([comb(v, 2) for v in c.values()])
for ai in a:
    print(summ - comb(c[ai], 2) + comb(c[ai] - 1, 2))

### FIXED CODE ###

import collections
import math


def comb(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


input()
a = list(map(int, input().split()))
c = collections.Counter(a)

summ = sum([comb(v, 2) for v in c.values()])
for ai in a:
    print(summ - c[ai] + 1)
### BUGGY CODE ###

from itertools import combinations
N = int(input())
scores = [int(input())for i in range(N)]
sums= sum(scores)
if sums % 10 != 0:
    print(sums)
    exit()
m = 0
flag = False
scores.sort()
for i in range(1,N):
    for j in combinations(scores,i):
        sj = sum(j)
        if (sums - sj) % 10 != 0:
            m = max(m, sums - sj)
            break
print(m)

### FIXED CODE ###

from itertools import combinations
N = int(input())
scores = [int(input())for i in range(N)]
sums= sum(scores)
if sums % 10 != 0:
    print(sums)
    exit()
scores.sort()
for i in range(N):
    if (sums-scores[i]) % 10 != 0:
        print(sums - scores[i])
        exit()
print(0)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[1]*N
for x in range(N):
  B[x]+=A.index(x+1)
for y in B:
  print(y,end="")
  if y!=B[N-1]:
    print(" ",end="")
print("\n")

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[1]*N
for x in range(N):
  B[A[x]-1]+=x
for y in B:
  print(y,end="")
  if y!=B[N-1]:
    print(" ",end="")
print("\n")
### BUGGY CODE ###

# ひとまず毎回ソートするバージョン
# Python 3, pypy ともにTLE
import bisect

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

for i in range(m):
	max_card, num = list(map(int, input().split() ))

	num_small = bisect.bisect(values, num)
	num_to_change = min(max_card, num_small)

	# sort
	new_values = values[num_to_change:num_small] + [num]*num_to_change + values[num_small:]
	values = new_values

print (sum(values))

### FIXED CODE ###

from operator import itemgetter
n, m = list(map(int, input().split() ))
values = list(map(int, input().split() ))
values.sort()

card_change = [list(map(int, input().split() )) for _ in range(m)]
card_change.sort(key = itemgetter(1))
# 変更後の数をkeyとしてソート

# X枚書き換えるとして、Xを全探索する方針で書いてみる
now = sum(values)
ans = sum(values)
idx = m - 1
for x in range(n):
	now -= values[x]

	card_change[idx][0] -= 1 # 変更可能枚数
	now += card_change[idx][1] # 変更後の値

	if now > ans:
		ans = now

	if card_change[idx][0] == 0:
		idx -= 1
		if idx < 0:
			break

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

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

ans = 1

for i in range(a,b+1):
  ans *= i
  
if ans > 0:
  print('Positive')
  
elif ans==0:
  print('Zero')
  
else:
  print('Negative')

### FIXED CODE ###

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

if a < 0 and b < 0:
  if (b-a)%2 == 1:
    print('Positive')
  else:
    print('Negative')

elif a>0:
  print('Positive')

else:
  print('Zero')
### BUGGY CODE ###

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

AA = []
for i,a in enumerate(A):
    AA.append(tuple([a,i]))

AA = sorted(AA,reverse=True)
DP =[]
for _ in range(N+1):
    DP.append([0]*(N+1))

for i,a in enumerate(AA):
    for x in range(i+1):
        y = i - x
        if x+ 1 <= N:
            DP[x+1][y] = max(DP[x+1][y], DP[x][y]+a[0]*abs(x-a[1]))
        if y+1 <= N:
            DP[x][y+1] = max(DP[x][y+1], DP[x][y]+a[0]*abs(N- 1 - y - a[1]))

MAX = 0
for x in range(N):
    y = N - x
    MAX = max(DP[x][y],MAX)

print(MAX)

### FIXED CODE ###

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

AA = []
for i,a in enumerate(A):
    AA.append(tuple([a,i]))

AA = sorted(AA,reverse=True)
DP =[]
for _ in range(N+1):
    DP.append([0]*(N+1))

for i,a in enumerate(AA):
    for x in range(i+1):
        y = i - x
        if x+ 1 <= N:
            DP[x+1][y] = max(DP[x+1][y], DP[x][y]+a[0]*abs(x-a[1]))
        if y+1 <= N:
            DP[x][y+1] = max(DP[x][y+1], DP[x][y]+a[0]*abs(N- 1 - y - a[1]))

MAX = 0
for x in range(N):
    y = N - x
    MAX = max(DP[x][y],MAX)

print(MAX)
### BUGGY CODE ###

n=int(input())
s=list(map(int,input().split()))
ex=0
t=[]
for i in s:
    if i in t:
        ex+=1
    else:
        t.append(i)

if ex%2==0:
    print(len(t))
else:
    print(len(t)-1)

### FIXED CODE ###

import collections
n=int(input())
s=list(map(int,input().split()))
k=len(collections.Counter(s))
if (n-k)%2==0:
    print(k)
else:
    print(k-1)
### BUGGY CODE ###

x = int(input())


y = x // 100
z = x % 100
t = 0
for i in range(101):
    if t == 1 or i>y:
        break
    for j in range(101):
        if t == 1 or i+j > y:
            break
        for k in range(101):
            if t == 1 or i+j+k > y:
                break
            for l in range(101):
                if t == 1 or i+j+k+l > y:
                    break
                for m in range(101):
                    if t == 1 or i+j+k+l+m > y:
                        break
                    for n in range(101):
                        if t == 1 or i+j+k+l+m+n > y:
                            break
                        if (i+j+k+l+m+n == y):
                            if i*0+j*1+k*2+l*3+m*4+n*5 == z:
                                t = 1
                                break
                        if (i+j+k+l+m+n > y):
                            break
if t == 1:
    print(1)
else:
    print(0)

### FIXED CODE ###

x = int(input())

x_ = x%100

t = 0
a = 5
while x_ != 0:
    t += x_//a
    x_ -= (x_//a)*a
    a -= 1


if x//100 >= t:
    print(1)
else:
    print(0)
### BUGGY CODE ###

def f(index, num):
  a[index][(0*10+num)%13]+=a[index-1][0]
  a[index][(0*10+num)%13]%=MOD
  a[index][(1*10+num)%13]+=a[index-1][1]
  a[index][(1*10+num)%13]%=MOD
  a[index][(2*10+num)%13]+=a[index-1][2]
  a[index][(2*10+num)%13]%=MOD
  a[index][(3*10+num)%13]+=a[index-1][3]
  a[index][(3*10+num)%13]%=MOD
  a[index][(4*10+num)%13]+=a[index-1][4]
  a[index][(4*10+num)%13]%=MOD
  a[index][(5*10+num)%13]+=a[index-1][5]
  a[index][(5*10+num)%13]%=MOD
  a[index][(6*10+num)%13]+=a[index-1][6]
  a[index][(6*10+num)%13]%=MOD
  a[index][(7*10+num)%13]+=a[index-1][7]
  a[index][(7*10+num)%13]%=MOD
  a[index][(8*10+num)%13]+=a[index-1][8]
  a[index][(8*10+num)%13]%=MOD
  a[index][(9*10+num)%13]+=a[index-1][9]
  a[index][(9*10+num)%13]%=MOD
  a[index][(10*10+num)%13]+=a[index-1][10]
  a[index][(10*10+num)%13]%=MOD
  a[index][(11*10+num)%13]+=a[index-1][11]
  a[index][(11*10+num)%13]%=MOD
  a[index][(12*10+num)%13]+=a[index-1][12]
  a[index][(12*10+num)%13]%=MOD
  
S=input()
N=len(S)
if N==1:
  if S=='?' or int(S)==5:
    print(1)
  else:
    print(0)
  exit()
  
MOD=10**9+7

a=[[0]*13 for i in range(N)]
if S[0]=='?':
  a[0]=[1]*10+[0]*3
else:
  a[0][int(S[0])]=1

for i in range(1, N):
  if S[i]=='?':
      f(i, 0)
      f(i, 1)
      f(i, 2)
      f(i, 3)
      f(i, 4)
      f(i, 5)
      f(i, 6)
      f(i, 7)
      f(i, 8)
      f(i, 9)
  else:
    f(i, int(S[i]))
    
print(a[-1][5])

### FIXED CODE ###

def f(index, num):
  for k in range(13):
    a[index][(k*10+num)%13]+=a[index-1][k]

S=input()
N=len(S)
if N==1:
  if S=='?' or int(S)==5:
    print(1)
  else:
    print(0)
  exit()
  
MOD=10**9+7

a=[[0]*13 for i in range(N)]
if S[0]=='?':
  a[0]=[1]*10+[0]*3
else:
  a[0][int(S[0])]=1

for i in range(1, N):
  if S[i]=='?':
    for j in range(10):
      f(i, j)
    for j in range(13):
      a[i][j]%=MOD
  else:
    f(i, int(S[i]))
    
print(a[-1][5])
### BUGGY CODE ###

n,a=int(input()),list(map(int,input().split()))
count=[0]*3
for i in a:count[i-1]+=1
#dp[i][j][k]...寿司が1個の皿がi枚、2個の皿がj枚、3個の皿がk枚の時の期待値
dp=[[[0]*(n+2) for i in range(n+2)]for i in range(n+2)]
for k in range(n+1):
  for j in range(n+1):
    for i in range(n+1):
      if i+j+k==0:continue
      #競プロフレンズ解説参照
      p=1
      if i>0:p+=dp[i-1][j][k]*(i/n)
      if j>0:p+=dp[i+1][j-1][k]*(j/n)
      if k>0:p+=dp[i][j+1][k-1]*(k/n)
      dp[i][j][k]=p/(1-((n-i-j-k)/n))
print(dp[count[0]][count[1]][count[2]])

### FIXED CODE ###

n,a=int(input()),map(int,input().split());c=[0]*3
for i in a:c[i-1]+=1
x,y,z=c;dp=[[[None]*(z+2) for i in range(n-x+2)]for i in range(n+2)];dp[0][0][0]=0
for k in range(z+1):
  for j in range(n-x-k+1):
    for i in range(n-k-j+1):
      if i+j+k:dp[i][j][k]=((dp[i-1][j][k]*i if i else 0)+(dp[i+1][j-1][k]*j if j else 0)+(dp[i][j+1][k-1]*k if k else 0)+n)/(i+j+k)
print(dp[x][y][z])
### BUGGY CODE ###

from math import sqrt
from collections import defaultdict
def main():
    # Load data
    N = int(input())
    A = list(map(int, input().split()))
    p = 10**9 + 7
    # LCM: dict 最小公倍数の素因数分解
    LCM = defaultdict(int)
    # A2Factor: dict A[i]の素因数分解
    A2Factor = [defaultdict(int) for _ in range(N)]
    
    def factorization(n, idx):
        """
        素因数分解
        """
        temp = n
        flag = 0
        for i in range(2, int(sqrt(n))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                flag = 1
                LCM[i] = max(LCM[i], cnt)
                A2Factor[idx][i] = cnt
        if temp!=1:
            LCM[temp] = max(LCM[temp], 1)
            A2Factor[idx][temp] = 1 
        if not flag:
            LCM[n] = max(LCM[n], 1)
            A2Factor[idx][n] = 1
        return LCM, A2Factor

    for idx in range(N):
        LCM, A2Factor = factorization(A[idx], idx)

    ans = 0
    for i in range(N):
        tmp = 1
        for key, value in LCM.items():
            cnt = 0 if key not in A2Factor[i].keys() else A2Factor[i][key]
            tmp *= pow(key, value-cnt, p)
            tmp %= p
        ans += tmp % p
        ans %= p

    print(ans % p)

main()

### FIXED CODE ###

from math import gcd

def lcm(a, b):
    return a*b//gcd(a,b)
def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10**9 + 7
    LCM = 1
    for a in A:
        LCM = lcm(LCM, a)
    ans = 0
    for a in A:
        ans += (LCM//a)
        

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

import sys
def Is(): return [int(x) for x in sys.stdin.readline().split()]

N,M,Q = Is()
lis = [[0]*(N+1) for _ in range(N+1)]
for i in range(M):
    l,r = Is()
    lis[l][r] += 1

dp = [[0]*(N+1) for _ in range(N+1)]

for _ in range(Q): 
    p,q = Is()
    t = 0
    for i in range(p,q+1):
        if dp[i][q]:
            t += dp[i][q]
        else:
            dp[i][q] = sum(lis[i][i:q+1])
            t += dp[i][q]
    print(t)
    

### FIXED CODE ###

import sys
def Is(): return [int(x) for x in sys.stdin.readline().split()]

N,M,Q = Is()
lis = [[0]*(N+1) for _ in range(N+1)]
for i in range(M):
    l,r = Is()
    lis[l][r] += 1

cs = [[0]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        cs[i][j] = cs[i][j-1] + sum(lis[i][:j+1])

for _ in range(Q): 
    p,q = Is()
    t = 0
    for i in range(p,q+1):
        t += cs[i][q] - cs[i][q-1]
    print(t)
### BUGGY CODE ###

card_num, gate_num = map(int, input().split())
table = [0] * card_num
count = 0


for i in range(gate_num):
    start_num, end_num = map(int, input().split())
    for j in range(start_num-1, end_num):
        table[j] += 1

for l in range(card_num):
    if table[l] == gate_num:
        count += 1

print(count)

### FIXED CODE ###

# 先頭の最大と最後尾の最小を求める
card_num, gate_num = map(int, input().split())
lmax, rmin = map(int, input().split()) # 最初の入力がlの最大とrの最小
for i in range(1, gate_num):
    l, r = map(int, input().split())
    lmax = max(lmax, l) # lmaxにlmaxとlの大きい方
    rmin = min(rmin, r) # rminにrminとrの小さい方
print(max(0, rmin-lmax+1)) # 0かrmin-lmax+1の大きい方を出力
### BUGGY CODE ###

# B
n = int(input())

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

maxa = 10 **18

ans = 1

for i in a:
  ans = ans * i

print(ans if maxa >= ans else -1)

### FIXED CODE ###

# B
n = int(input())

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

  

  

maxa = 10 **18

ans = 1
if min(a) == 0:
  ans = 0

for i in a:
  ans = ans * i
  if ans > maxa:
    print(-1)
    break
else:
  print(ans)
### BUGGY CODE ###

import collections

n = int(input())

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

a.sort()

if a[0] != 1:
    i = 0

    while i < len(a):
        a = [x for x in a if (not float.is_integer(x / a[i])) or ((x / a[i]) == 1)]

        i += 1

    num_dict = dict(collections.Counter(a))

    counts = num_dict.values()

    temp = dict(collections.Counter(counts))

    print(temp.get(1, 0))

elif (len(a) > 1) and (a[0] == a[1]):
    print(0)
else:
    print(1)

### FIXED CODE ###

n = int(input())

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

a.sort()

dp = [True] * (a[-1] + 1)

ans = 0

m = a[-1]

for i, x in enumerate(a[:-1]):
    if not a[i+1] == x and dp[x]:
        ans += 1
    for b in range(x, m + 1, x):
        dp[b] = False

if dp[a[-1]]:
    ans += 1

print(ans)