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

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
B=[list(map(int,input().split())) for i in range(Q)]
from bisect import bisect_left
# def 二分探索(リスト, 要素)
def index(lst, e):
    # Step 1. bisect_left して
    i = bisect_left(lst, e)
    
    # Step 2. 変な値を ValueError で弾いて
    if i == len(lst):
        return -1
    if lst[i] != e:
        return -1
    # Step 3. 値を返す。
    return i
def quick_sort(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr

    # データの状態に左右されないためにrandom.choice()を用いることもある。
    # ref = random.choice(arr)
    ref = arr[0]
    ref_count = 0

    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [ref] * ref_count + right
A=quick_sort(A)

for i in B:
    j=1
    while j!=-1:
        j=index(A,i[0])
        if not j==-1:
            A[j]=i[1]
        A=quick_sort(A)
    print(sum(A))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
B=[list(map(int,input().split())) for i in range(Q)]

dp=[0 for i in range(1,10**6)]
for i in A:
    dp[i]+=1
S=sum(A)
for i in B:
    S+=(i[1]-i[0])*dp[i[0]]
    print(S)
    dp[i[1]]+=dp[i[0]]
    dp[i[0]]=0
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
ans=0
q=[(1+pp)/2 for pp in p]
for i in range(k,n+1):
    ans=max(ans,sum(q[i-k:i]))
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
ans=0
q=[0]
for  i in p:
    q.append((1+i)/2)
from itertools import accumulate
q=list(accumulate(q))
for i in range(k,n+1):
    ans=max(ans,q[i]-q[i-k])
print(ans)
### BUGGY CODE ###

n = int(input())
aList = list(map(int, input().split()))
aLen = len(aList)
aSet = sorted(list(set(aList)))
aSum = 0
for a in aSet:
    aCount = aList.count(a)
    if aCount > a:
        aSum += aCount - a
    if aCount < a:
        aSum += aCount
    # aLen -= aCount
    # if a > aLen:
    #     aSum += aLen
    #     break

print(aSum)


### FIXED CODE ###

n = int(input())
aList = list(map(int, input().split()))
aLen = len(aList)
aSet = sorted(list(set(aList)))
aSum = 0
for a in aSet:
    aCount = aList.count(a)
    if aCount > a:
        aSum += aCount - a
    if aCount < a:
        aSum += aCount
    aLen -= aCount
    if a > aLen:
        aSum += aLen
        break

print(aSum)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

ct = 0
R, G, B, N = na()
for r in range((N // R) + 1):
    for g in range((N // G) + 1):
        if N < r * R + g * G:
            break
        elif (N - r * R - g * G) % B == 0:
            ct += 1
print(ct)


### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

ct = 0
R, G, B, N = na()
for r in range((N // R) + 1):
    for g in range((N // G) + 1):
        if N < r * R + g * G:
            break
        elif (N - r * R - g * G) % B == 0:
            ct += 1
print(ct)
### BUGGY CODE ###

s = input()
k = int(input())

k_list = set(s)
for i in range(2, len(s)+1):
    for j in range(len(s)+1-i):
        sub = s[j:j+i]
        k_list.add(sub)
        if len(k_list) > k * len(s):
            break
    if len(k_list) > k * len(s):
        break

k_list = list(k_list)
k_list.sort()
print(k_list[k-1])

### FIXED CODE ###

s = input()
k = int(input())

kn = len(s) * k
k_list = set(s)

for i in range(2, k+1):
    for j in range(len(s)):
        k_list.add(s[j:j+i])

k_list = list(k_list)
k_list.sort()
print(k_list[k-1])
### BUGGY CODE ###

n, k = list(map(int, input().split()))
l = [0 for i in range(k)]
ans = 0
M = 10**9 + 7

def dev(n):
    dl = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            dl.append(i)
            if i != n // i:
                dl.append(n//i)
    dl.sort()
    return dl

for i in range(k, 0, -1):
    a=k//i
    b=a**n
    l[i-1] += b
    d=dev(i)
    for m in d:
        if m != i:
            l[m-1] -= l[i-1]

for i in range(1, k+1):
    ans+=i*l[i-1]

print(ans%M)


### FIXED CODE ###

n, k = list(map(int, input().split()))
l = [0 for i in range(k)]
ans = 0
M = 10**9 + 7

# def dev(n):
#     dl = []
#     for i in range(1, int(n**0.5)+1):
#         if n % i == 0:
#             dl.append(i)
#             if i != n // i:
#                 dl.append(n//i)
#     dl.sort()
#     return dl

for i in range(k, 0, -1):
#     a=k//i
#     b=a**n%M
    b=pow(k//i, n, M)
    for j in range(i*2, k+1, i):
        b -= l[j-1]
    l[i-1] = b%M

for i in range(1, k+1):
    ans+=i*l[i-1]

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

n=int(input())
s=input()
cnt=0
r=s.count("R")
g=s.count("G")
b=s.count("B")

ans=r*g*b

for i in range(n):
    for j in range(n):
        if s[i]!=s[j]:
            if j-i<=n//2:
                if i<j:
                    for k in range(n):
                        if s[k]!=s[j] and s[i]!=s[k]:
                            if j<k:
                                if j-i==k-j:
                                    ans-=1
                    
print(ans)
        

### FIXED CODE ###

n=int(input())
s=input()
cnt=0
r=s.count("R")
g=s.count("G")
b=s.count("B")

ans=r*g*b

for i in range(n):
    for j in range(n):
        if s[i]!=s[j]:
            if j-i<=n//2:
                if i<j:
                    d=j-i
                    k=j+d
                    if k<n:
                        if s[k]!=s[j] and s[i]!=s[k]:
                            ans-=1
                        

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

from itertools import product
n, y = map(int, input().split())
found = False
for i in product(range(n+1),repeat=3):
  if sum(i) == n and 10000*i[0]+5000*i[1]+1000*i[2] == y:
    print(i[0], i[1], i[2])
    found = True
    break
if not found:
  print("-1 -1 -1")

### FIXED CODE ###

n, y = map(int, input().split())
found = False
for i in range(n+1):
  for j in range(n+1-i):
    if i + j+ (n-i-j) == n and 10000*i+5000*j+1000*(n-i-j) == y:
        print(i, j, n-i-j)
        found = True
        break
  else:
    continue
  break 
if not found:
  print("-1 -1 -1")
### BUGGY CODE ###

K = int(input())

num = ""
cnt = 0
ans = False

while range(10000000):
    num = int(num + "7")
    cnt += 1
    if num % K == 0:
        ans = True 
        print(cnt)
        break
    else:
        num = str(num)
    
if ans == False :
    print(-1)

### FIXED CODE ###

K = int(input())

cnt = 0
a = 0
ans = False

for i in range(K):
    a = 10 * a +7
    cnt += 1
    if a % K == 0 :
        print(cnt)
        ans = True
        break
    else:
        a = a % K

if ans == False:
    print(-1)
### BUGGY CODE ###

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



sum = 0
D = set(range(N))
E = set()
for i in D:
    E.add(i)
    for j in D - E:
        sum += A[i] * A[j]

print(sum % (10**9+7))

### FIXED CODE ###

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


S = []
sum = 0
for i in range(N):
    sum += A[i]
    S.append(sum)

ans = 0
for i in range(N):
    ans += A[i] * (S[N-1] - S[i])

print(int(ans % (10**9 + 7)))
### BUGGY CODE ###

from itertools import permutations

INF=1145141919810

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

road=[[0 if x==y else INF for y in range(N+1)] for x in range(N+1)]

for _ in range(M):
	a,b,c=map(int,input().split())
	road[a][b] = road[b][a] = c

for k in range(N+1):
	for i in range(N+1):
		for j in range(N+1):
			road[i][j] = min(road[i][j], road[i][k] + road[k][j])

print(min(sum(road[p[i-1]][p[i]] for i in range(1, R)) for p in permutations(r)))


### FIXED CODE ###

from itertools import product, permutations

INF=1145141919810

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

road=[[0 if x==y else INF for y in range(N+1)] for x in range(N+1)]

for _ in range(M):
	a,b,c=map(int,input().split())
	road[a][b] = road[b][a] = c

for k in range(N+1):
	for i in range(N+1):
		for j in range(N+1):
			road[i][j] = min(road[i][j], road[i][k] + road[k][j])

print(min(sum(road[p[i-1]][p[i]] for i in range(1, R)) for p in permutations(r)))
### BUGGY CODE ###

def root(uf, x):
    if uf[x] == x:
        return x
    else:
        uf[x] = root(uf, uf[x])
        return uf[x]

def same(uf, x, y):
    return root(uf, x) == root(uf, y)

def unite(uf, x, y):
    rx = root(uf, x)
    ry = root(uf, y)
    if rx == ry:
        return
    uf[rx] = ry

N, M = map(int,input().split())
p = list(map(int,input().split()))
p.insert(0, -1)
uf = [i for i in range(N+1)]
for i in range(M):
    a, b = (map(int,input().split()))
    unite(uf, a, b)
for i in range(1, N+1):
    root(uf, i)

ans = 0
match = [[] for i in range(N+1)]
for i in range(1, N+1):
    match[uf[i]].append(i)
for i in range(1, N+1):
    matchlen = len(match[i])
    for j in range(matchlen):
        if p[match[i][j]] in match[i]:
            ans += 1
print(str(ans))

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def root(x):
    if uf[x] == x:
        return x
    else:
        uf[x] = root(uf[x])
        return uf[x]

def same(x, y):
    return root(x) == root(y)

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    uf[rx] = ry

N, M = map(int,readline().split())
p = list(map(int,readline().split()))
p.insert(0, -1)
uf = [i for i in range(N+1)]
for i in range(M):
    a, b = (map(int,readline().split()))
    unite(a, b)
for i in range(1, N+1):
    root(i)

ans = 0
#N += 1
#match = [[] for i in range(N)]
#for i in range(1, N):
#    match[uf[i]].append(i)
#for i in range(1, N):
#    matchlen = len(match[i])
#    for j in range(matchlen):
#        if p[match[i][j]] in match[i]:
#            ans += 1

for i in range(1, N+1):
    if same(i, p[i]):
        ans += 1
print(str(ans))
### BUGGY CODE ###

#from fractions import Fraction
from math import ceil
from heapq import heappush, heappop

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

A_queue = []
for a in input().split():
	a = float(a)
	heappush(A_queue, (-a, a, 1))

# search smallest i such that f(i) == True
def auto_bisearch_smallest(f, s = None):
	if s == None:
		s = 0
		w = -1
		while f(s) == True:
			s = w
			w *= 2
	e = s
	w = 1
	while f(e) == False:
		e = s + w
		w *= 2
	
	return bisearch_smallest(f, s, e + 1)

# search smallest i ( s <= i < e ) such that f(i) == True
def bisearch_smallest(f, s, e = None):
	if e == None:
		e = s - 1
		s = 0
	else:
		e -= 1
	
	while s < e:
		m = (s + e) // 2
		if f(m):
			e = m
		else:
			s = m + 1
	
	if s == e and f(s):
		return s
	else:
		return -1

def calc(K):
	while K > 0:
		length, a, div = heappop(A_queue)
		if len(A_queue) > 0:
			ref = A_queue[0][0]
			new_div = auto_bisearch_smallest(lambda div: -a / div > ref, div)
			K -= (new_div - div)
			heappush(A_queue, (-a / new_div, a, new_div))
		else:
			div += K
			K = 0
			heappush(A_queue, (-a / div, a, div))
	return -A_queue[0][0]

print(ceil(calc(K)))


### FIXED CODE ###

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

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

# search smallest i such that f(i) == True
def auto_bisearch_smallest(f, s = None):
	if s == None:
		s = 0
		w = -1
		while f(s) == True:
			s = w
			w *= 2
	e = s
	w = 1
	while f(e) == False:
		e = s + w
		w *= 2
	
	return bisearch_smallest(f, s, e + 1)

# search smallest i ( s <= i < e ) such that f(i) == True
def bisearch_smallest(f, s, e = None):
	if e == None:
		e = s - 1
		s = 0
	else:
		e -= 1
	
	while s < e:
		m = (s + e) // 2
		if f(m):
			e = m
		else:
			s = m + 1
	
	if s == e and f(s):
		return s
	else:
		return -1

def calc(length):
	count = 0
	for a in A_list:
		if a > length:
			if a % length == 0:
				count += (a // length) - 1
			else:
				count += a // length
	return count

print(auto_bisearch_smallest(lambda length: calc(length) <= K, 1))
### BUGGY CODE ###

n,k,q = map(int,input().split())
point = [k]*(n)
for _ in range(q):
    a = int(input())
    for i in range(n):
        if a-1 == i:
            pass
        else:
            point[i] -= 1
for i in range(n):
    if point[i] > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

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

S = list(input())
dp = [[0 for _ in range(13)] for _ in range(len(S)+1)]
dp[0][0]=1
#print(dp[15][5])
for i in range(len(S)):
  a = 0
  if S[i]=="?":
    for j in range(10):
      for k in range(13):
        dp[i+1][(k*10+j)%13] += dp[i][k]
  else:
    a = int(S[i])
    for k in range(13):
      dp[i+1][(k*10+a)%13] += dp[i][k]
print(dp[len(S)][5]%(10**9+7))

### FIXED CODE ###

S = list(input())
dp = [[0 for _ in range(13)] for _ in range(len(S)+1)]
dp[0][0]=1
#print(dp[15][5])
for i in range(len(S)):
  a = 0
  if S[i]=="?":
    for j in range(10):
      for k in range(13):
        dp[i+1][(k*10+j)%13] += dp[i][k]
  else:
    a = int(S[i])
    for k in range(13):
      dp[i+1][(k*10+a)%13] += dp[i][k]
  for k in range(13):
    dp[i + 1][k] %= (10**9+7)
print(dp[len(S)][5])
### BUGGY CODE ###

N=int(input())
a = list(sorted(map(int,input().split())))
# print(a)

result = []
# all +
if a[0] > 0:
    if len(a) == 2:
        print(a[1]-a[0])
        print(a[1], a[0])
        exit()
    result.append((a[0], a[1]))
    t = a[0]-a[1]
    a.pop(0)
    a[0] = t
# all -
elif a[-1] < 0:
    if len(a) == 2:
        print(a[0]-a[1])
        print(a[0], a[1])
        exit()
    result.append((a[-1], a[-2]))
    t = a[-1]-a[-2]
    a.pop(-1)
    a[-1] = t

# print(a)
b = []
for i in range(len(a)-1):
    if a[i] > 0:
        result.append((b[0], a[i]))
        t = b[0]-a[i]
        b[0] = t
    else:
        b.append(a[i])
b.append(a[-1])
# print(b)
while len(b) != 1:
    result.append((b[-1], b[0]))
    b.append(b[-1]-b[0])
    b.pop(0)
    b.pop(-2)
# print(b)

print(b[0])
for r in result:
    print(r[0],r[1])

### FIXED CODE ###

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

result = []
# all +
if a[0] > 0:
    if len(a) == 2:
        print(a[1]-a[0])
        print(a[1], a[0])
        exit()
    result.append((a[0], a[1]))
    t = a[0]-a[1]
    a.pop(0)
    a[0] = t
# all -
elif a[-1] < 0:
    if len(a) == 2:
        print(a[0]-a[1])
        print(a[0], a[1])
        exit()
    result.append((a[-1], a[-2]))
    t = a[-1]-a[-2]
    a.pop(-1)
    a[-1] = t

# print(a)
b = []
for i in range(len(a)-1):
    if a[i] > 0:
        result.append((b[0], a[i]))
        t = b[0]-a[i]
        b[0] = t
    else:
        b.append(a[i])
b.append(a[-1])
# print(b)
while len(b) != 1:
    result.append((b[-1], b[0]))
    b.append(b[-1]-b[0])
    b.pop(0)
    b.pop(-2)
# print(b)

print(b[0])
for r in result:
    print(r[0],r[1])
### BUGGY CODE ###

import numpy as np
import sys
import math

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

k = int(input())


def gcd(a,b):
    if a > b:
        a , b = b , a

    # q = b / a
    r = b % a

    if r == 0:
        return a
    else:
        return gcd(a,r)
    

ans = 0

for i in range(1,k+1):
    for j in range(1,k+1):
        x = gcd(i,j)
        for l in range(1,k+1):
            ans += gcd(x,l)

print(ans)

### FIXED CODE ###

import numpy as np
import sys
import math

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

data = [2246640
,2332104
,2379085
,2434833
,2490534
,2554600
,2609625
,2693919
,2742052
,2813988
,2875245
,2952085
,3003306
,3096024
,3157249
,3224511
,3306240
,3388576
,3444609
,3533637
,3591322
,3693924
,3767085
,3842623
,3912324
,4027884
,4102093
,4181949
,4270422
,4361548
,4427853
,4548003
,4616104
,4718640
,4812789
,4918561
,5003286
,5131848
,5205481
,5299011
,5392008
,5521384
,5610705
,5739009
,5818390
,5930196
,6052893
,6156139
,6239472
,6402720
,6493681
,6623853
,6741078
,6864016
,6953457
,7094451
,7215016
,7359936
,7475145
,7593865
,7689630
,7886244
,7984165
,8130747
,8253888
,8403448
,8523897
,8684853
,8802826
,8949612
,9105537
,9267595
,9376656
,9574704
,9686065
,9827097
,9997134
,10174780
,10290813
,10493367
,10611772
,10813692]


k = int(input())

if k >= 119:
    print(data[k-119])
    sys.exit()


def gcd(a,b):
    if a > b:
        a , b = b , a

    # q = b / a
    r = b % a

    if r == 0:
        return a
    else:
        return gcd(a,r)
    

sum = 0



for i in range(k):
    for j in range(k):
        for l in range(k):
            sum += gcd(i+1,gcd(j+1,l+1))


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

# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline

## input
N,Q = map(int, readl().rstrip().split())
STX = [list(map(int, readl().rstrip().split())) for _ in range(N)]
Dn = [None for _ in range(Q+1)]
for i in range(Q):
  Dn[i] = int(readl().rstrip())
Dn[Q] = 10**10
ans = []


## solve
for s,t,x in sorted(STX,key=lambda x:x[2]):
  l = r = bisect_left(Dn,s-x)
  t -= x
  while Dn[r] < t:
    heappush(ans, (Dn[r],x))
    r += 1
  del Dn[l:r]

for d in Dn[:-1]:
  heappush(ans, (d,-1))


## output
for _ in range(Q):
  print(heappop(ans)[1])    


### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

n=int(input())
a = list(map(int, input().split()))
ans=1
for i in a:
    ans*=i
    if ans == 0:
        break
if ans > 10 ** 18:
    ans=-1
print(ans)

### FIXED CODE ###

n=int(input())
a = list(map(int, input().split()))
a.sort()
ans=1
b=10**18
for i in a:
    ans*=i
    if ans > b:
        ans=-1
        break
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
flags = [False for i in range(n)]
nums = [0 for i in range(n)]
day = 0
flag = True
while False in flags:
    if flag == False:
        break
    match = set()
    for i in range(n):
        if nums[i] == n - 1 or i in match:
            continue
        num = a[i][nums[i]] - 1
        if nums[num] == n - 1:
            flag = False
            break
        if num in match:
            continue
        if a[num][nums[num]] - 1 == i:
            match.add(i)
            match.add(num)
            nums[i] += 1
            nums[num] += 1
            if nums[i] == n - 1:
                flags[i] = True
            if nums[num] == n - 1:
                flags[num] = True
    if not match:
        flag = False
        break
    day += 1
if flag == True:
    print(day)
else:
    print(-1)

### FIXED CODE ###

import sys, collections
input = sys.stdin.readline

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
nums = [0 for i in range(n)]
day = 0
match = 0
flag = True
queue = collections.deque([])
temp = set()
for i in range(1, n + 1):
    i2 = a[i - 1][0]
    if a[i2 - 1][0] == i:
        if i not in temp:
            queue.append([i, i2])
            temp.add(i)
            temp.add(i2)
if not queue:
    flag = False
while queue:
    temp = []
    while queue:
        test = queue.popleft()
        match += 1
        num1, num2 = test[0], test[1]
        nums[num1 - 1] += 1
        nums[num2 - 1] += 1
        temp.append(num1)
        temp.append(num2)
    flag2 = False
    temp2 = set()
    for i in temp:
        if nums[i - 1] <= n - 2:
            new_num = a[i - 1][nums[i - 1]]
            if nums[new_num - 1] <= n - 2 and a[new_num - 1][nums[new_num - 1]] == i:
                if i not in temp2:
                    queue.append([i, new_num])
                    flag2 = True
                    temp2.add(i)
                    temp2.add(new_num)
    if flag2 == False and match < n * (n - 1) // 2:
        flag = False
        break
    day += 1

if flag == True:
    print(day)
else:
    print(-1)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
import numpy as np

num_count = [0]*(10**5+1)
num_count = np.array(num_count)
tmp = np.arange(10**5+1)
for i in A:
    num_count[i] += 1

for q in range(Q):
    B,C = map(int,input().split())
    num_count[C] += num_count[B]
    num_count[B] = 0
    ans = np.dot(tmp,num_count)
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
import numpy as np

num_count = [0]*(10**5+1)
num_count = np.array(num_count)
tmp = np.arange(10**5+1)
tmp_sum = sum(A)
for i in A:
    num_count[i] += 1

for q in range(Q):
    B,C = map(int,input().split())
    tmp_C = C*(num_count[B])
    tmp_B = B*(num_count[B])
    num_count[C] += num_count[B]
    num_count[B] = 0
    tmp_sum = tmp_sum + tmp_C - tmp_B
    print(tmp_sum)
### BUGGY CODE ###

from functools import reduce

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

def lcm(a,b):
    return a*b//gcd(a,b)

def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

n = int(input())
l = [int(_) for _ in input().split()]
x = lcm_list(l)
ans = 0
for i in range(n):
    ans += x // l[i]
    ans %= (10**9 + 7)
print(ans)

### FIXED CODE ###

import fractions
from functools import reduce

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


n = int(input())
l = [int(_) for _ in input().split()]
x = lcm_list(l)
ans = 0
for i in range(n):
    ans += x // l[i]
ans %= (10**9 + 7)
print(ans)
### BUGGY CODE ###

n, m, p = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(m)]

for i in range(m):
    lst[i][2] = - (lst[i][2] - p)

def bellmanford():
    rep = 0
    while rep < n:
        update = False
        for edge in lst:
            a,b,c = edge
            if d[a] != 10**100 and d[b] > d[a]+ c:
                d[b] = d[a] + c
                update = True
        if not update:
            break
        rep += 1
    return False if rep != n else True

not_N_reach_list = []
not_1_reach_list = []
for i in range(1, n):
    d = [10**100] * (n+1)
    d[i] = 0
    bellmanford()
    if i == 1:
        for j in range(2, n):
            if d[j] == 10**100:
                not_1_reach_list.append(j)
    else:
        if d[n] == 10**100:
            not_N_reach_list.append(i)
        
exclude_lst = set(not_N_reach_list + not_1_reach_list)

new_lst = []
for edge in lst:
    a, b, c = edge
    if a not in exclude_lst and b not in exclude_lst:
        new_lst.append(edge)
        
lst = new_lst

d = [10**100] * (n+1)
d[1] = 0
a = bellmanford()
if a:
    print(-1)
else:
    print(0) if -d[n] < 0 else print(-d[n])

### FIXED CODE ###

n, m, p = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(m)]
 
for i in range(m):
    lst[i][2] = - (lst[i][2] - p)

d = [10**100] * (n+1)
d[1] = 0
rep = 0
 
while True:
    update = False
    for edge in lst:
        a,b,c = edge
        if d[a] != 10**100 and d[b] > d[a]+ c:
            if rep >= n:
                d[b] = -10**100
            else:
                d[b] = d[a] + c
            update = True
    if not update:
        break
    rep += 1
    if rep > 2*n:
        break

if d[n] <= - 10**100:
    print(-1)
elif -d[n] < 0:
    print(0)
else:
    print(-d[n])