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

N = int(input())
A = list(map(int, input().split()))
 
def gcd(a,b):
  if b==0:
    return a
  else:
  	return gcd(b, a%b)
 
def gcd_list(X):
  dmy=gcd(X[0],X[1])
  dmy=X[0]*X[1]
  for i in range(len(X)):
    dmy=gcd(dmy,X[i])
  return dmy
 
if N==2:
  print(max(A))
else:
  R=[]
  for i in range(N):
    C=A[:i]
    C.extend(A[i+1:])
    R.append(gcd_list(C))
 
  print(int(max(R)))

### FIXED CODE ###

def gcd(a,b):
    if b == 0:
        return a
    if a % b == 0:
        return b
    else:
        return gcd(b,a%b)

N = int(input())
A = [i for i in map(int,input().split())]
L = [0]
R = [0]
for i in range(N):
    L.append(gcd(L[-1],A[i]))
for i in range(N-1,-1,-1):
    R.append(gcd(R[-1],A[i]))
R.reverse()
g = []
for i in range(N):
    g.append(gcd(L[i],R[i+1]))
print(max(g))
### BUGGY CODE ###

N, M = map(int, input().split())
L = []
R = []
ans = 0
tmp = 1
for _ in range(M):
    inp = input().split()
    L.append(int(inp[0]))
    R.append(int(inp[1]))
for j in range(1,N + 1):
    for i in range(M):
        if tmp == 1:
            if L[i]-1 < j < R[i]+1:
                tmp *= 1
            else:
                tmp *= 0
        else:
            break
    if tmp == 1:
        ans += 1
    else:
        tmp = 1
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
L = []
R = []
ans = 0
for _ in range(M):
    inp = input().split()
    L.append(int(inp[0]))
    R.append(int(inp[1]))
L_max = max(L)
R_min = min(R)
for i in range(L_max,min(R_min,N) + 1):
    ans  += 1
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(input().split())
count = 0
tmp = 1
check = []
for _ in range(n - k + 1):
    for i in range(k):
        tmp *= int(a[i + count])
    check.append(tmp)
    tmp = 1
    count += 1

for j in range(n - k):
    if check[j] < check[j + 1]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n, k = input().split()
n = int(n)
k = int(k)
a = [int(s) for s in input().split()]
sums = []
K = k - 1
for i in range(K,n - 1):
    if(a[i - K] < a[i + 1]):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n = int(input())
charar = input()
charlist = []
while len(list(set(list(charar)))) >1:
    for i in range(len(charar)-1):
        if charar[i] != charar[i+1]:
            charlist.append(charar[:i+1])
            charar = charar[i+1:]
            break
print(len(charlist)+1)

### FIXED CODE ###

n = int(input())
charar = input()
sum = 0
for i in range(len(charar) - 1):
    if charar[i] != charar[i + 1]:
        sum +=1
print(sum+1)
### BUGGY CODE ###

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

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

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

print(dp[-1])

### FIXED CODE ###

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

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

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

print(dp[-1])
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

# dp[i][smaller][d] : i桁目で、K未満で、そこまでの総和をDで割った余り = 個数

K = readline().rstrip()
D = int(readline())
DIV = 10 ** 9 + 7
keta = len(K)

dp = [[[0] * D for i in range(2)] for j in range(keta)]

x0 = int(K[0])
dp[0][0][x0 % D] = 1
bef = x0 % D # 未満じゃないときに直前に値が入っているmodを記録しておく
for i in range(x0):
  dp[0][1][i % D] += 1
  
for i in range(1, keta):
  x = int(K[i])
  
  # 未満じゃない -> 未満じゃない
  dp[i][0][(bef + x) % D] = 1
  
  # 未満じゃない -> 未満
  # 0~x-1の値を取り得る
  for j in range(x):
    dp[i][1][(bef + j) % D] += dp[i - 1][0][bef]
  
  for j in range(D):
    dp[i][1][j] %= DIV
  
  bef = (bef + x) % D # 未満じゃないときに値が入っているmodを記録
  
  # 未満 -> 未満
  for j in range(D):
    for k in range(10): # 0~9のすべてを取れる
      dp[i][1][(k + j) % D] += dp[i - 1][1][j]
      
  for j in range(D):
    dp[i][1][j] %= DIV

print((dp[-1][0][0] + dp[-1][1][0] - 1) % DIV) # 0を数えないので引く

### FIXED CODE ###

import sys
readline = sys.stdin.readline

# dp[i][smaller][d] : i桁目で、K未満で、そこまでの総和をDで割った余り = 個数

K = readline().rstrip()
D = int(readline())
DIV = 10 ** 9 + 7
keta = len(K)

dp = [[[0] * D for i in range(2)] for j in range(keta)]

x0 = int(K[0])
dp[0][0][x0 % D] = 1
bef = x0 % D # 未満じゃないときに直前に値が入っているmodを記録しておく
for i in range(x0):
  dp[0][1][i % D] += 1
  
for i in range(1, keta):
  x = int(K[i])
  
  # 未満じゃない -> 未満じゃない
  dp[i][0][(bef + x) % D] = 1
  
  # 未満じゃない -> 未満
  # 0~x-1の値を取り得る
  for j in range(x):
    dp[i][1][(bef + j) % D] += dp[i - 1][0][bef]
  
  for j in range(D):
    dp[i][1][j] %= DIV
  
  bef = (bef + x) % D # 未満じゃないときに値が入っているmodを記録
  
  # 未満 -> 未満
  for j in range(D):
    for k in range(10): # 0~9のすべてを取れる
      dp[i][1][(k + j) % D] += dp[i - 1][1][j]
      
  for j in range(D):
    dp[i][1][j] %= DIV

print((dp[-1][0][0] + dp[-1][1][0] - 1) % DIV) # 0を数えないので引く
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline

n = int(input())
a = int(input())

color = [a]
color_min = a

for _ in range(1, n):
    a = int(input())
    if color_min >= a:
        bisect.insort_left(color, a)
        color_min = a
    else:
        j = bisect.bisect_left(color, a)
        del color[j-1]
        bisect.insort_left(color, a)
        color_min = color[0]

print(len(color))


### FIXED CODE ###

from collections import deque
from bisect import bisect_left

n = int(input())
a = [int(input()) for _ in range(n)]

b = deque([])

for ai in a:
    if len(b) == 0:
        b.append(ai)
    else:
        if ai <= b[0]:
            b.appendleft(ai)
        else:
            idx = bisect_left(b, ai)
            b[idx-1] = ai

print(len(b))
### BUGGY CODE ###

N,K=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(N)]
x=[]
y=[]
for i,j in z:
    x.append(i)
    y.append(j)
x.sort()
y.sort()
a=10**20
for i in range(N):
    for j in range(i+1,N):
        for k in range(N):
            for l in range(k+1,N):
                l,r,d,u=x[i],x[j],y[k],y[l]
                if sum([l<=v<=r and d<=w<=u for v,w in z])>=K:
                    a=min(a,(r-l)*(u-d))
print(a)

### FIXED CODE ###

n,k=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(n)]
z.sort()
a=10**20
for i in range(n):
    for j in range(i+1,n):
        x=z[j][0]-z[i][0]
        l=sorted(t[1]for t in z[i:j+1])
        for u,v in zip(l,l[k-1:]):
            a=min(a,x*(v-u))
print(a)
### BUGGY CODE ###

N = int(input())
l = []
c=0
for i in range(N):
    s = input()
    ss = sorted(s)
    for te in l:
        if ss == te:
            c+=1
    l.append(ss)
print(c)


### FIXED CODE ###

N = int(input())
l = []
c=0
for i in range(N):
    l.append(sorted(input()))
l.sort()

base =0
next = 1
ren = 1
while True:
    if l[base] == l[next]:
        ren += 1
        next += 1
    else:
        c += ren * (ren - 1) // 2
        base = next
        next += 1
        ren = 1
    if next == N:
        c += ren * (ren-1) // 2
        break
print(c)
### BUGGY CODE ###

import sys
from copy import deepcopy

def main():
    INF = 10**18
    input = sys.stdin.readline
    N, M, L = [int(x) for x in input().split()]
    d = [set() for _ in range(N+1)]
    cs = [[INF] * (N+1) for _ in range(N+1)]
    for _ in range(M):
        A, B, C = [int(x) for x in input().split()]
        d[A].add(B)
        d[B].add(A)
        cs[A][B] = C
        cs[B][A] = C

    #ds = [[INF] * (N+1) for in range(N+1)]:
    ds = deepcopy(cs)
    bs = [[INF] * (N+1) for _ in range(N+1)]
    for k in range(1, N+1):
        for i in range(1, N+1):
            for j in range(1, N+1):
                ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j])
                if ds[i][j] <= L:
                    bs[i][j] = 1

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

    Q, = [int(x) for x in input().split()]
    for _ in range(Q):
        s, t = [int(x) for x in input().split()]
        print(bs[s][t]-1 if bs[s][t] < INF else -1)


if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
from copy import deepcopy

def main():
    INF = 10**18
    input = sys.stdin.readline
    N, M, L = [int(x) for x in input().split()]
    d = [set() for _ in range(N+1)]
    ds = [[INF] * (N+1) for _ in range(N+1)]
    bs = [[INF] * (N+1) for _ in range(N+1)]
    for _ in range(M):
        A, B, C = [int(x) for x in input().split()]
        A, B = sorted([A, B])
        d[A].add(B)
        if L >= C:
            ds[A][B] = C

    nes = set()
    for k in range(1, N+1):
        for i in range(1, N+1):
            for j in range(i+1, N+1):
                ds[i][j] = min(ds[i][j], ds[min(i, k)][max(i, k)] + ds[min(k, j)][max(k, j)])
                if ds[i][j] <= L:
                    bs[i][j] = 1

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

    Q, = [int(x) for x in input().split()]
    for _ in range(Q):
        s, t = sorted(int(x) for x in input().split())
        print(bs[s][t]-1 if bs[s][t] < INF else -1)


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


N = int(input())

A = list(map(int, input().split()))
ans = 0

plus = []
minus = []

for i, j in enumerate(A):
    plus.append(i+j)
    minus.append(i-j)

for i in plus:
    for j in minus:
        if i == j:
            ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())

A = list(map(int, input().split()))
ans = 0

plus = []
minus = []

for i, j in enumerate(A):
    # print(i, j)
    plus.append(i+j)
    minus.append(i-j)

# print(plus)
# print(minus)

plus_count = Counter(plus)
minus_count = Counter(minus)
# print(plus_count)
# print(minus_count)


for i,j in plus_count.items():
    # print(i, j)
    if i in minus_count:
        ans += j * minus_count[i]
        # print(i, j)
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
t = [0]
v = 0
if n > m:
    mod = [0] * m
    for i in range(len(a)):
        v += a[i]
        mod[v%m] += 1
    ans = mod[0]
    for i in range(m):
        ans += mod[i] * (mod[i]-1) / 2
    print(int(ans))
else:
    ans = 0
    for i in range(len(a)):
        v += a[i]
        t.append(v)
    for i in range(len(t)-1):
        for j in range(i+1, len(t)):
            if (t[j]-t[i]) % m == 0:
                ans += 1
    print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
t = [0]
v = 0
b = {0:1}
for i in range(n):
    v = (v + a[i]) % m
    if v in b.keys():
        b[v] += 1
    else:
        b[v] = 1
ans = 0
for i in b.values():
    ans += i * (i-1) / 2
print(int(ans))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
s = list(input())
n =len(s)-1
A=13
data=[4,3,12,9,10,1]*n
data=data[-n:]

dp=[[0 for i in range(A+1)] for j in range(n+1)]
dp[0][0]=1

def benri(a,i):
	return a*data[i]%A


for i in range(n):
	for j in range(A+1):
		if s[i]!="?":
			if j-benri(int(s[i]),i)>=0:
				dp[i+1][j]=dp[i][j-benri(int(s[i]),i)]
			else:
				dp[i+1][j]=dp[i][j-benri(int(s[i]),i)+13]

		else:
			for c in range(10):
				if j-benri(c,i)>=0:
					dp[i+1][j]+=dp[i][j-benri(c,i)]
				else:
					# print(j-c%13+13)
					dp[i+1][j]+=dp[i][j-benri(c,i)+13]

			
			
# print(data)
print(dp[n][5]%(10**9+7))
				


### FIXED CODE ###

S = input()
dp = [[0]*13 for i in range(len(S))]
MOD = 10**9+7
 
if S[0]=='?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(S[0])] = 1
 
for i,c in enumerate(S[1:]):
    for j in range(13):
        if c=='?':
            for k in range(10):
                nj = (j*10 + k) % 13
                dp[i+1][nj] += dp[i][j]
                dp[i+1][nj] %= MOD
        else:
            nj = (j*10 + int(c)) % 13
            dp[i+1][nj] += dp[i][j]
            dp[i+1][nj] %= MOD
 
print(dp[-1][5])
### BUGGY CODE ###

a = input()
b = a.replace("ST","")
while "ST" in b:
    b = b.replace("ST","")
print(len(b))

### FIXED CODE ###

a = input()
s,t = 0,0
for i in a:
    if i == "S":
        s += 1
    else:
        if s==0:
            t += 1
        else:
            s -=1
print(s+t)
### BUGGY CODE ###

a, b = map(int,input().split())
lim = a * b +1
for i in range(min(a,b),lim):
    if i % a == 0 and i % b == 0:
        print(i)
        quit()

### FIXED CODE ###

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

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
ans = a * b / gcd(a,b)
print(int(ans))
### BUGGY CODE ###

from functools import reduce

n = int(input())

a = list(map(int,input().split()))
new = reduce(lambda x, y: x*y, a)
val = pow(10,18)
if new > val:
	print(-1)
else:
	print(new)	 


### FIXED CODE ###

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

import sys

def ep(*params):
    print(*params,file=sys.stderr)

l = ''
r = ''

S = input().rstrip()

Q = int(input())
mode = 0
for _ in range(Q):
    ope = list(input().split())
    if ope[0] == '1':
        mode = (mode + 1)%2
    else:
        op = (int(ope[1]) + mode)%2
        if op == 1:
            l += ope[2]
        else:
            r += ope[2]
    print(mode,l[::-1],S,r,sep=":",file=sys.stderr)    

if mode == 0:
    print(l[::-1],S,r,sep="")    
else:
    print(r[::-1],S[::-1],l,sep="")    


### FIXED CODE ###

import sys

def ep(*params):
    print(*params,file=sys.stderr)

l = ''
r = ''

S = input().rstrip()

Q = int(input())
mode = 0
for _ in range(Q):
    ope = list(input().split())
    if ope[0] == '1':
        mode = (mode + 1)%2
    else:
        op = (int(ope[1]) + mode)%2
        if op == 1:
            l += ope[2]
        else:
            r += ope[2]
    #print(mode,l[::-1],S,r,sep=":",file=sys.stderr)    

if mode == 0:
    print(l[::-1],S,r,sep="")    
else:
    print(r[::-1],S[::-1],l,sep="")
### BUGGY CODE ###

n=int(input())
s=[input() for i in range(n)]

a=[]
c=0

for i in s:
    if i not in a:
        a.append(i)
        c+=1

print(c)

### FIXED CODE ###

n=int(input())
s=[input() for i in range(n)]

s=set(s)

print(len(s))
### BUGGY CODE ###

S = input()
Q = int(input())
query = [list(input().split()) for _ in range(Q)]

ans = list(S)
for i in range(Q):
    if query[i][0] == '1':
        ans = ans[::-1]
        continue
    elif query[i][0] == '2':
        f = query[i][1]
        c = query[i][2]
        if f == '1':
            ans = [c] + ans
        else:
            ans = ans + [c]
print(''.join(ans))


### FIXED CODE ###

import sys
input = sys.stdin.readline

S = input().rstrip()
Q = int(input())
head = ''
tail = ''
rev = False

for _ in range(Q):
    query = list(input().split())
    if query[0] == '1':
        if rev:
            rev = False
        else:
            rev = True
    elif query[0] == '2':
        f = query[1]
        c = query[2].rstrip()
        if f == '1':
            if rev:
                tail = tail + c
            else:
                head = c + head
        else:
            if rev:
                head = c + head
            else:
                tail = tail + c
if rev:
    tmp = head + S + tail
    print(tmp[::-1])
else:
    print(head + S + tail)
### BUGGY CODE ###

from collections import deque
n,m,k=map(int,input().split())
flag=[0]*(n+1)
friend=[[] for i in range(n+1)]
block=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int, input().split())
    friend[a].append(b)
    friend[b].append(a)

for i in range(k):
    a, b = map(int, input().split())
    block[a].append(b)
    block[b].append(a)

d=deque()
m=1
for i in range(1,n+1):
    if flag[i]==0:
        d.append(i)
        flag[i]=m
        while len(d)>0:
            a=d.popleft()
            for j in range(len(friend[a])):
                if flag[friend[a][j]]!=m:
                    flag[friend[a][j]]=m
                    d.append(friend[a][j])
        m+=1
#print(flag)
#print(friend)
#print(block)
answer=[0]*n
for i in range(1,n+1):
    a=sum(x==flag[i] for x in flag)
    b=len(friend[i])+1
    c=0
    for x in range(1,n+1):
        if flag[x]==flag[i] and (x in block[i]):
            c+=1
    #print(a,b,c)
    answer[i-1]=a-b-c

print(" ".join(map(str, answer)))

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m,k=map(int, input().split())
friend=[[] for i in range(n+1)]
block_count=[0]*(n+1)
uf=UnionFind(n+1)
for i in range(1,m+1):
    a,b=map(int, input().split())
    friend[a].append(b)
    friend[b].append(a)
    uf.union(a,b)

for i in range(1,k+1):
    a,b=map(int, input().split())
    if uf.same(a,b)==True:
        block_count[a]+=1
        block_count[b] += 1

answer=[0]*(n)
for i in range(1,n+1):
    answer[i-1]=uf.size(i)-len(friend[i])-block_count[i]-1
    #print(uf.size(i))

print(" ".join(map(str,answer)))
#print(friend)
#print(uf)
#print(block_count)
### BUGGY CODE ###

N,M = map(int,input().split())
LRC = [list(map(int,input().split())) for _ in range(M)]

def dijkstra(s,n,cost):
  #始点sから各頂点への最短距離
  #n:頂点数,　cost[u][v] : 辺uvのコスト(存在しないときはinf)
  d = [float("inf")] * n
  used = [False] * n
  d[s] = 0

  while True:
    v = -1
    #まだ使われてない頂点の中から最小の距離のものを探す
    for i in range(n):
      if (not used[i]) and (v == -1):
        v = i
      elif (not used[i]) and d[i] < d[v]:
        v = i
    if v == -1:
      break
    used[v] = True

    for j in range(n):
      d[j] = min(d[j],d[v]+cost[v][j])
  return d

INF = float('inf')
G = [[INF for _ in range(N)] for _ in range(N)]

for i in range(N-1):
  G[i+1][i] = 0
for l,r,c in LRC:
  l -= 1
  r -= 1
  G[l][r] = c
#print(G)

#print(dijkstra(0,N,G))
p = dijkstra(0,N,G)[N-1]
print(p if p != INF else -1)

### FIXED CODE ###

class SegmentTree:
  def __init__(self, size, default, op = min):
    self.size = 2**size.bit_length()
    self.dat = [default]*(self.size*2)
    self.op = op

  def update(self, i, x):
    i += self.size
    self.dat[i] = x
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

  def add(self, i, x):
    i += self.size
    self.dat[i] = self.op(self.dat[i], x)
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i], x)

  def get(self, a, b = None):
    if b is None:
      b = a + 1
    l, r = a + self.size, b + self.size
    res = None
    while l < r:
      if l & 1:
        if res is None:
          res = self.dat[l]
        else:
          res = self.op(res, self.dat[l])
        l += 1

      if r & 1:
        r -= 1
        if res is None:
          res = self.dat[r]
        else:
          res = self.op(res, self.dat[r])
      l >>= 1
      r >>= 1
    return res

N,M = map(int,input().split())
LRC = [list(map(int,input().split())) for _ in range(M)]
LRC.sort(key=lambda x:(x[0],x[1]))
#print(LRC)

INF = 10**18
dp = SegmentTree(N,INF,min)
dp.update(0,0)
#print(dp.get(0,1))

for l,r,c in LRC:
  p = dp.get(l-1,r-1)+c
  # cf.https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/1109_nikkei2019-2-qual
  #for i in range(l,r):
  #  if p < dp.get(i):
  #    dp.update(i,p)
  if p < dp.get(r-1):
    dp.update(r-1,p)
print(dp.get(N-1) if dp.get(N-1) != INF else -1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline 
sys.setrecursionlimit(10 ** 6)

def main():
  N,M = map(int,input().split())
  path = [[] for i in range(N)]
  inf = 10 ** 6 * 2
  ans = [[None,inf] for i in range(N - 1)]
  
  for _ in range(M):
    a,b = map(int,input().split())
    a = a - 1
    b = b - 1
    path[a].append(b)
    path[b].append(a)
  
  def dfs(cur,par,con):
    if con == M + 1:
      return
    for chi in path[cur]:
      if chi == par:
        continue
      if con < ans[chi - 1][1]:
        ans[chi - 1][0] = cur
        ans[chi - 1][1] = con + 1
        dfs(chi,cur,con + 1)
  
  dfs(0,-1,0)
  
  if all([i[0] != None for i in ans]):
    print("Yes")
    for i in range(N - 1):
      print(ans[i][0] + 1)
  else:
    print("No")

if __name__=='__main__':
  main()

### FIXED CODE ###

from collections import deque

import sys
input = sys.stdin.readline 

N,M = map(int,input().split())
path = [[] for i in range(N)]
ans = [None for i in range(N)]
visited = [0 for i in range(N)]

for _ in range(M):
  a,b = map(int,input().split())
  a = a - 1
  b = b - 1
  path[a].append(b)
  path[b].append(a)

def bfs(path, root,visited):
  visited[root] = 1
  queue = deque([root])
  while queue:
    cur = queue.popleft()
    for chi in path[cur]:
      if visited[chi] == 1:
        continue
      else:
        ans[chi] = cur + 1
        visited[chi] = 1
        queue.append(chi)

  if all([i == 1 for i in visited]):
    return "Yes"
  else:
    return "No"
  
flag = bfs(path,0,visited)

print(flag)

if flag == "Yes":
  for i in range(1,N):
    print(ans[i])
### BUGGY CODE ###

n, m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]

x = 0
ans = 0


while x < n:
    p = 10000000
    for i in range(m):
        if a[i][0] >= x:
            p = min(p, a[i][1])
    if p <= n:
        ans +=1
    if p == 10000000:
        break
    x = p

print(ans)

### FIXED CODE ###

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

l = []

for i in range(m):
    a, b = map(int, input().split())
    l.append([b, a])

l.sort()

ans = 0
x = 0

for i in range(m):
    if l[i][1] >= x:
        ans += 1
        x = l[i][0]

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

import sys
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return list(map(int, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]


NN = 10 ** 6 + 100
primes = []
isprime = [True for _ in range(NN + 1)]
min_factor = [-1 for _ in range(NN + 1)]
#エラトステネスの篩
for i in range(2, NN + 1):
    if not isprime[i]:
        continue
    primes.append(i)
    min_factor[i] = i
    for j in range(i * 2, NN + 1, i):
        isprime[j] = False
        if min_factor[j] == -1:
            min_factor[j] = i

def prime_factrize(n):
    res = []
    while n != 1:
        prime = min_factor[n]
        exp = 0
        while min_factor[n] == prime:
            exp += 1
            n //= prime
        res.append([prime, exp])
    return res

n = INT()
a = LIST()

ll = []
for i in range(n):
    aa = prime_factrize(a[i])
    for j in range(len(aa)):
        flag = True
        for k in range(len(ll)):
            if aa[j][0] == ll[k][0]:
                ll[k][1] = max(ll[k][1], aa[j][1])
                flag = False
        if flag:
            ll.append(aa[j])
l = 1
for i in range(len(ll)):
    l *= pow(ll[i][0], ll[i][1], mod)
ans = 0
for i in range(n):
    ans += l // a[i]
    ans %= mod
print(ans)


### FIXED CODE ###

import sys
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return list(map(int, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n = INT()
a = LIST()
l = 1
for i in a:
    l = lcm(l, i)
l %= mod
ans = 0
for i in a:
    ans += l * pow(i, mod - 2, mod)
print(ans % mod)