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

from collections import deque
from sys import stdin
def create_groups(n, links):
  from builtins import len, set
  group_set = {}
  groups = [-1 for _ in range(n)]
  group_number = 0
  d = deque()
  for i in range(n):
    if groups[i] == -1:
      group_member = []
      d.append(i)
      while len(d) != 0:
        j = d.popleft()
        groups[j] = group_number
        group_member.append(j)
        for k in links[j]:
          if groups[k] == -1:
            d.append(k)
      group_set[group_number] = set(group_member)
      group_number += 1
  return groups, group_set
def read_links(n, k):
  from builtins import int, map
  readline = stdin.readline
  links = [[] for _ in range(n)]
  for i in range(k):
    p, q = map(int, readline().split())
    links[p - 1].append(q - 1)
    links[q - 1].append(p - 1)
  return links
def main():
  from builtins import len
  n, k, l = map(int, input().split())
  road_links = read_links(n, k)
  train_links = read_links(n, l)
  road_groups, road_set = create_groups(n, road_links)
  train_groups, train_set = create_groups(n, train_links)
  print(*[len(road_set[road_groups[i]] & train_set[train_groups[i]]) for i in range(n)])
main()


### FIXED CODE ###

from sys import stdin

def find(parent, i):
  if parent[i] == i:
    return i
  parent[i] = find(parent, parent[i])
  return parent[i]

def unite(parent, i, j):
  i = find(parent, i)
  j = find(parent, j)
  if i == j:
    return
  parent[i] = j

n, k, l = map(int, stdin.readline().split())

roads = list(range(n))
rails = list(range(n))

for i in range(k):
  p, q = map(int, stdin.readline().split())
  unite(roads, p - 1, q - 1)

for i in range(l):
  p, q = map(int, stdin.readline().split())
  unite(rails, p - 1, q - 1)

d = {}
for i in range(n):
  t = (find(roads, i), find(rails, i))
  if t in d:
    d[t] += 1
  else:
    d[t] = 1

print(*[d[(find(roads, i), find(rails, i))] for i in range(n)])
### BUGGY CODE ###

from itertools import combinations

S = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

a = 1
d = 0

for s in S:
    d = d + int(s)*a
    num = d%2019
    counts[num] += 1
    a *= 10

ans = 0

for i in counts:
    if i >=2:
        x = len(list(combinations(list(range(i)),2)))
        ans += x

print(ans)

### FIXED CODE ###

#ACの人のやつ丸パクリです。自分のソースコードがTLEになるので試しに使わせてもらいます。

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

from collections import deque
import numpy as np

H, W = list(map(int, input().split()))
field = [[i=='#' for i in input()] for _ in range(H)]
count = 0

def bfs():
  global count
  q = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])
  while True:
    nq = deque()
    while len(q) > 0:
      y, x = q.popleft()
      for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0<=ny<H and 0<=nx<W and not field[ny][nx]:
          field[ny][nx] = True
          nq.append((ny, nx))
    if len(nq) > 0:
      q = nq
    else:
      break
    count += 1
      
bfs()
print(count)

### FIXED CODE ###

from collections import deque
import copy

def main():
  H, W = map(int, input().split())
  maps = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if maps[i][j]])
  count = 0
  while True:
    nq = deque()
    while q:
      x, y = q.popleft()
      if x > 0 and not maps[x-1][y]:
        maps[x-1][y] = True
        nq.append((x-1,y))
      if y > 0 and not maps[x][y-1]:
        maps[x][y-1] = True
        nq.append((x,y-1))
      if x < H-1 and not maps[x+1][y]:
        maps[x+1][y] = True
        nq.append((x+1,y))
      if y < W-1 and not maps[x][y+1]:
        maps[x][y+1] = True
        nq.append((x,y+1))
    if nq:
      q = copy.copy(nq)
    else:
        break
    count += 1
  print(count)

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

num, poi, ans = [int(x) for x in input().split()]
"""
print(num)
print(poi)
print(ans)
"""

list01 = []
while num > 0:
  list01.append(poi)
  num -= 1

i = 1
while i <= ans:
  list01 = [x -1 for x in list01]
  #print("i=",i)
  j = int(input())
  #print("j=",j)
  list01[j -1] += 1
  i += 1

#print(list01)
  
for k in list01:
  if k <= 0:
    print("No")
  else:
    print("Yes")


### FIXED CODE ###

num, poi, ans = [int(x) for x in input().split()]

list01 = [poi for x in range(num)]
list02 = [0 for x in range(num)]

for i in range(ans):
  j = int(input())
  list02[j-1] += 1

for i in range(num):
  list02[i] = list02[i] + list01[i] - ans

for k in list02:
  if k <= 0:
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

import sys
s=input()
t=input()

def c(a,b,s,t):
    li=""
    j=0
    for i in s:
        if i==a:
            li+=b
            if t[j]!=b:
                print("No")
                sys.exit()
        elif i==b:
            li+=a
        else:
            li+=i
        j+=1
    return li
    

for i in range(len(t)):
    if s[i]!=t[i]:
        s=c(s[i],t[i],s,t)
    
        

if s==t:
    print("Yes")
else:
    print("No")
        
    

### FIXED CODE ###

s=input()
t=input()


def f(s):
    l=[]
    a="abcdefghijklmnopqrstuvwxyz"
    r=""
    for i in range(len(s)):
        if s[i] in l:
            for j in range(len(l)):
                if s[i]==l[j]:
                    r+=a[j]
        else:
            r+=a[len(l)]
            l.append(s[i])
    return r

if f(s)==f(t):
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N, M, P = map(int, input().split())
E = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    E[i] = (a - 1, b - 1, P - c)

d = [float("inf") for _ in range(N)]
d[0] = 0
for i in range(N):
    for f, t, w in E:
        if d[f] != float("inf") and d[t] > d[f] + w:
            d[t] = d[f] + w
for i in range(N):
    for f, t, w in E:
        if d[f] != float("inf") and d[t] > d[f] + w:
            d[t] = -float("inf")
if d[-1] == -float("inf"):
    print(-1)
elif d[-1] > 0:
    print(0)
else:
    print(-d[-1])

### FIXED CODE ###

N, M, P = map(int, input().split())
E = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    E[i] = (a - 1, b - 1, P - c)
INF = float("inf")
d = [INF for _ in range(N)]
d[0] = 0
for i in range(2*N):
    for f, t, w in E:
        if d[t] > d[f] + w:
            d[t] = d[f] + w
            if i >= N:
                d[t] = -INF
    if i == N-1:
        dN = d[-1]
if dN != d[-1]:
    print(-1)
elif dN > 0:
    print(0)
else:
    print(-dN)
### BUGGY CODE ###

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

k = [1+lis.index(l) for l in range(1,n+1)]

print(*k)


### FIXED CODE ###

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

for i, item in enumerate(lis):
    a[item - 1] = i + 1

print(*a)
### BUGGY CODE ###

N = int(input())
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
        else:
            self.parents[xRoot] = yRoot
            if self.size[xRoot] == self.size[yRoot]:
                self.size[yRoot]+=1
tree = UnionFind(N)

xList = []
yList = []
for i in range(1,N+1):
    x,y = map(int,input().split())
    xList.append((x,i))
    yList.append((y,i))
xList.sort()
yList.sort()
edges = []
for i in range(1,N):
    edges.append((xList[i][0]-xList[i-1][0],xList[i-1][1],xList[i][1]))
    edges.append((yList[i][0]-yList[i-1][0],yList[i-1][1],yList[i][1]))
edges.sort()
cost = 0
for e in edges:
    w,s,t = e
    if tree.find(s) != tree.find(t):
        tree.unite(s,t)
        cost += w

print(cost)

### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(2000000)
    input = sys.stdin.readline

    class UnionFind():
        def __init__(self,n):
            self.n=n
            self.parents = [i for i in range(n+1)]
            self.size = [1]*(n+1)
        def find(self,x):
            if self.parents[x]==x:
                return x
            else:
                self.parents[x]=self.find(self.parents[x])
                return self.parents[x]
        def unite(self,x,y):
            xRoot = self.find(x)
            yRoot = self.find(y)
            if xRoot == yRoot:
                return
            if self.size[xRoot]>self.size[yRoot]:
                self.parents[yRoot] = xRoot
            else:
                self.parents[xRoot] = yRoot
                if self.size[xRoot] == self.size[yRoot]:
                    self.size[yRoot]+=1

    N = int(input())
    nodesX = []
    nodesY = []
    for i in range(1,N+1):
        x,y = map(int,input().split())
        nodesX.append((x,i))
        nodesY.append((y,i))
    nodesX.sort()
    nodesY.sort()
    edges = []
    for i in range(1,N):
        edges.append((nodesX[i][0]-nodesX[i-1][0],nodesX[i][1],nodesX[i-1][1]))
        edges.append((nodesY[i][0]-nodesY[i-1][0],nodesY[i][1],nodesY[i-1][1]))
    edges.sort()
    tree = UnionFind(N)
    cost = 0
    for w,s,t in edges:
        if tree.find(s)!= tree.find(t):
            tree.unite(s,t)
            cost += w
    print(cost)

main()
### BUGGY CODE ###

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

### FIXED CODE ###

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

n, k = map(int, input().split())
if k > n:
    k = n
A = [int(i) for i in input().split()]
INF = 10 ** 12
dp = [INF] * n

dp[0] = 0
for i in range(1, n):
    for j in range(1, k + 1):
        dp[i] = min(dp[i], dp[i - j] + abs(A[i] - A[i - j]))
    
print(dp[-1])

### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
H = np.array(list(map(int, input().split())))
dp = np.zeros(n, dtype = int)

for i in range(1, n):
    s = max(i - k, 0)
    dp[i] = min(dp[s : i] + abs(H[i] - H[s : i]))
    
print(dp[-1])
### BUGGY CODE ###

H,W=map(int,input().split())
S=[input() for i in range(H)]
A=[[0]*W for i in range(H)]
B=[[0]*W for i in range(H)]
for i in range(H):
    s=0
    t=0
    num=0
    while t<W:
        #print(s,t,num)
        if S[i][t]=='#':
            for k in range(s,t):
                A[i][k]=num
            num=0
            t+=1
            s=t
        else:
            t+=1
            num+=1
    for k in range(s,t):
        A[i][k] = num
for j in range(W):
    s=0
    t=0
    num=0
    while t<H:
        #print(s,t,num)
        if S[t][j]=='#':
            for k in range(s,t):
                B[k][j]=num
            num=0
            t+=1
            s=t
        else:
            t += 1
            num += 1
    for k in range(s,t):
        B[k][j] = num
#print(A)
#print(B)
ans=0
for i in range(H):
    for j in range(W):
        if S[i][j]=='.':
            ans=max(ans,A[i][j]+B[i][j]-1)
print(ans)



### FIXED CODE ###

H,W=map(int,input().split())
S=[input() for i in range(H)]
A=[[0]*W for i in range(H)]
B=[[0]*W for i in range(H)]
for i in range(H):
    s=0
    t=0
    num=0
    while t<W:
        #print(s,t,num)
        if S[i][t]=='#':
            for k in range(s,t):
                A[i][k]=num
            num=0
            t+=1
            s=t
        else:
            t+=1
            num+=1
    for k in range(s,t):
        A[i][k] = num
for j in range(W):
    s=0
    t=0
    num=0
    while t<H:
        #print(s,t,num)
        if S[t][j]=='#':
            for k in range(s,t):
                B[k][j]=num
            num=0
            t+=1
            s=t
        else:
            t += 1
            num += 1
    for k in range(s,t):
        B[k][j] = num
#print(A)
#print(B)
ans=0
for i in range(H):
    for j in range(W):
        if S[i][j]=='.':
            ans=max(ans,A[i][j]+B[i][j]-1)
print(ans)
### BUGGY CODE ###

def bin_digit(n: int):
    return len(bin(n)[2:]) + 1


MOD = 10**9 + 7

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

digit = bin_digit(max(An))

res = 0
for d in range(digit):
    n0, n1 = 0, 0
    for i in range(N):
        if An[i] & 1 << d:
            n1 += 1
        else:
            n0 += 1

    temp = 2**d % MOD
    n = n0 * n1 % MOD
    temp *= n % MOD
    res = (res + temp) % MOD

print(res)


### FIXED CODE ###

def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K = K * x
            x = x ** 2
            n = (n - 1) // 2
        else:
            x = x ** 2
            n = n // 2

    return K * x


MOD = 10**9 + 7

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

res = 0
for d in range(60):
    n0, n1 = 0, 0
    for i in range(N):
        if (An[i] >> d) & 1:
            n1 += 1
        else:
            n0 += 1

    temp = pow_k(2, d) % MOD
    temp *= (n0*n1) % MOD
    res = (res + temp) % MOD

print(res)
### BUGGY CODE ###

N = int(input())
slist = []
for i in range(N):
    slist.append(''.join(sorted(list(input()))))

i = 0
count = 0
for s in slist:
    i += 1
    for target in slist[i:]:
        if target == s:
            count += 1

print(count)


### FIXED CODE ###

from scipy.special import comb

N = int(input())
sdict = {}
for i in range(N):
    inp = ''.join(sorted(list(input())))
    if inp not in sdict:
        sdict.update({inp:1})
    else:
        sdict[inp] += 1

ans = 0
for key in sdict:
    ans += comb(sdict[key], 2 , exact=True)

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

S = list(input())
T = list(input())
N = len(S)

X = []
Y = []
for i in range(N):
    X.append(S.count(S[i]))
    Y.append(T.count(T[i]))

print('Yes' if X == Y else 'No')

### FIXED CODE ###

S = list(input())
T = list(input())
N = len(S)

a = ord('a')
alf = []
for i in range(26):
     alf.append(chr(a))
     a += 1

SN = [[] for i in range(26)]
TN = [[] for i in range(26)]
for i in range(N):
    for j in range(26):
        if alf[j] == S[i]:
            SN[j].append(i)
        if alf[j] == T[i]:
            TN[j].append(i)
SN.sort()
TN.sort()
print('Yes' if SN == TN else 'No')
### BUGGY CODE ###

def resolve():
	n, k = map(int, input().split())
	h = list(map(int, input().split()))
	dp = [float('inf')]*n
	dp[0], dp[1] = 0, abs(h[0] - h[1])
	for i in range(2, n):
		s = []
		for j in range(1, k+1):
			if i-j >= 0:
				s.append(dp[i-j] + abs(h[i-j] - h[i]))
		dp[i] = min(s)
	print(dp[-1])
resolve()

### FIXED CODE ###

def resolve():
	n, k = map(int, input().split())
	h = list(map(int, input().split()))
	dp = [float('inf')]*n
	dp[0], dp[1] = 0, abs(h[0] - h[1])
	for i in range(2, n):
		s = []
		for j in range(1, k+1):
			if i-j >= 0:
				s.append(dp[i-j] + abs(h[i-j] - h[i]))
		dp[i] = min(s)
	print(dp[-1])
resolve()
### BUGGY CODE ###

def binary_search(cards,n,number):
    low=0
    high=len(cards)-1

    while high-low>1:
        mid=(low+high)//2
        base=cards[mid]
        if base==number:
            for i in range(n):
                cards.insert(mid,number)
            return cards
        if base<number:
            low=mid
        else:
            high=mid

    if cards[high]==cards[low]:
        if number>cards[high]:
            for i in range(n):
                cards.insert(high+1, number)
        else:
            for i in range(n):
                cards.insert(low, number)
    else:
        for i in range(n):
            cards.insert(high,number)
    return cards

#1 3 5 7 9 11 <=8
#1 3 [5] 7 9 11 <= 8
#1 3 (5) 7 9 (11) <=8
#1 3 5 [7] 9 11 <= 8
#1 3 5 (7) 9 (11) <= 8
#1 3 5 7 [9] 11 <= 8
#1 3 5 (7) (9) 11
#1 3 5 [7] 9 11 <=8
#1 3 5 (7)

def main():
    inp1=list(map(lambda x:int(x),input().split()))
    cards=list(map(lambda x:int(x),input().split()))
    N=inp1[0]
    M=inp1[1]
    B=[]
    C=[]
    for i in range(M):
        changes=list(map(lambda x:int(x),input().split()))
        B.append(changes[0])
        C.append(changes[1])

    cards.sort()

    for i in range(M):
        cards=binary_search(cards,B[i],C[i])

    cards=cards[len(cards)-N:len(cards)]

    print(sum(cards))

if __name__=="__main__":
    main()

### FIXED CODE ###

from heapq import heappush,heappop

def main():
    inp1=list(map(lambda x:int(x),input().split()))
    cards=list(map(lambda x:int(x),input().split()))
    cards_heap=[]
    for i in cards:
        heappush(cards_heap,i)

    N=inp1[0]
    M=inp1[1]
    B=[]
    C=[]
    for i in range(M):
        changes=list(map(lambda x:int(x),input().split()))
        B.append(changes[0])
        C.append(changes[1])

    cb=zip(C,B)
    cb=sorted(cb,reverse=True)


    for C,B in cb:
        for _ in range(B):
            a=heappop(cards_heap)
            if C>a:
                heappush(cards_heap,C)
            else:
                heappush(cards_heap,a)
                break

    print(sum(cards_heap))

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

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
C=[]

for _ in range(H):
    C.append(list(input()))

def keiro(x,y,cn,k):
    nx=[]

    i=1
    while True:
        if y+i>W-1 or i>k:
            break
        elif C[x][y+i]=='.' or C[x][y+i]==str(cn+1):
            C[x][y+i]=str(cn+1)
            nx.append([x,y+i])
            i+=1
        else:
            break
    
    i=1
    while True:
        if y-i<0 or i>k:
            break
        elif C[x][y-i]=='.' or C[x][y-i]==str(cn+1):
            C[x][y-i]=str(cn+1)
            nx.append([x,y-i])
            i+=1
        else:
            break
    
    i=1
    while True:
        if x+i>H-1 or i>k:
            break
        elif C[x+i][y]=='.' or C[x+i][y]==str(cn+1):
            C[x+i][y]=str(cn+1)
            nx.append([x+i,y])
            i+=1
        else:
            break
    
    i=1
    while True:
        if x-i<0 or i>k:
            break
        elif C[x-i][y]=='.' or C[x-i][y]==str(cn+1):
            C[x-i][y]=str(cn+1)
            nx.append([x-i,y])
            i+=1
        else:
            break

    return nx

C[x1-1][y1-1]=str(0)
taisho=keiro(x1-1,y1-1,0,K)
result=1

while C[x2-1][y2-1]=='.':
    next_taisho=[]
    if len(taisho)==0:
        result=-1
        break
    for l in taisho:
        m=keiro(l[0],l[1],result,K)

        for n in m:
            next_taisho.append(n)
    result+=1
    taisho=next_taisho.copy()

print(result)

### FIXED CODE ###

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
C=[]
nx=set([])

for _ in range(H):
    C.append(list(input()))

def keiro(x,y,k):
    i=1
    while True:
        if y+i>W-1 or C[x][y+i]!='.' or i>k:
            break
        else:
            if (x,y+i) not in nx:
                nx.add((x,y+i))
            i+=1
    
    i=1
    while True:
        if y-i<0 or C[x][y-i]!='.' or i>k:
            break
        else:
            if (x,y-i) not in nx:
                nx.add((x,y-i))
            i+=1
    
    i=1
    while True:
        if x+i>H-1 or C[x+i][y]!='.' or i>k:
            break
        else:
            if (x+i,y) not in nx:
                nx.add((x+i,y))
            i+=1
    
    i=1
    while True:
        if x-i<0 or C[x-i][y]!='.' or i>k:
            break
        else:
            if (x-i,y) not in nx:
                nx.add((x-i,y))
            i+=1

    return 0

C[x1-1][y1-1]=0
keiro(x1-1,y1-1,K)
taisho=nx.copy()
result=1
for j in nx:
    C[j[0]][j[1]]=result

while C[x2-1][y2-1]=='.':
    nx=set([])
    if len(taisho)==0 or result>10**6:
        result=-1
        break
    for l in taisho:
        keiro(l[0],l[1],K)
    result+=1
    for j in nx:
        C[j[0]][j[1]]=result
    taisho=nx.copy()

print(result)
### BUGGY CODE ###

import re

a = input()
a = re.split(" ",a)

b = input()
b = re.split(" ",b)
b = list(map(int,b))
c = set(b)
d = list(map(int,c))
if(len(b) <= int(a[1])):
    print(0)
else:
    save = []
    for i in range(len(d)):
        x = b.count(d[i])
        save.append(int(x))
    save.sort()
    y = len(d)-int(a[1])
    ans = 0
    for i in range(int(y)):
        ans += int(save[i])
    print(ans)


### FIXED CODE ###

import re
import collections

a = input()
a = re.split(" ",a)
b = input()
b = re.split(" ",b)

c = collections.Counter(b)

c = sorted(c.items(), key=lambda x: x[1])
ans = 0
for i in range(len(c)-int(a[1])):
    ans += c[i][1]
print(ans)
### BUGGY CODE ###

k,s = [int(i) for i in input().split()]
r=0

for i in range(0,k+1):
    for j in range(0,k+1):
        for l in range(0,k+1):
            if s-(i+j)==l:
                r+=1

print(r)


### FIXED CODE ###

k,s = [int(i) for i in input().split()]
r=0

for i in range(0,k+1):
    for j in range(0,k+1):
        if 0<=s-(i+j)<=k:
            r+=1

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

n = int(input())
#x = {i: int(j) for i, j in enumerate(input().split())}
#y = list(x.values())
x = [int(i) for i in input().split()]
y = x.copy()
y.sort()
e = y[n//2 - 1]
o = y[n//2]
for xx in x:
    if y.index(xx) >= n//2:
        print(e)
    else:
        print(o)

### FIXED CODE ###

n = int(input())
x = [int(i) for i in input().split()]
y = x.copy()
y.sort()
y_e = y[n//2]
y_o = y[n//2 - 1]
for xx in x:
    if xx >= y_e:
        print(y_o)
    else:
        print(y_e)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
from fractions import gcd
from functools import reduce

def gcd_list(numbers):
    return reduce(gcd, numbers)
def lcm_base(x, y):
    return (x * y) // gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def main():
    N = int(input())
    A = sorted([int(i) for i in input().split()])
    MOD = 10**9+7

    GCD = gcd_list(A)
    LCM = lcm_list(A)
    ans = 0
    if GCD != 1 and LCM == A[-1]:
        for i in range(N):
            ans = (ans + A[-1] // A[i]) % MOD
    else:
        for i in range(N):
            ans = (ans + LCM // A[i]) % MOD

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from fractions import gcd
from functools import reduce

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]
# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

def gcd_list(numbers):
    return reduce(gcd, numbers)
def lcm_base(x, y):
    return (x * y) // gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def main():
    N = int(input())
    A = sorted([int(i) for i in input().split()])
    MOD = 10**9+7

    GCD = gcd_list(A)
    LCM = lcm_list(A) % MOD
    ans = 0
    if GCD != 1 and LCM == A[-1]:
        for i in range(N):
            ans = (ans + A[-1] * mod_inv(A[i],MOD)) % MOD
    else:
        for i in range(N):
            ans = (ans + LCM * mod_inv(A[i],MOD)) % MOD

    print(ans)

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

n=int(input())
a=list(map(int,input().split()))
c=0
L=[[0,0],[a[0],a[0]]]
for i in range(1,n):
    L.append([L[-1][0]^a[i],L[-1][1]+a[i]])
for l in range(1,n):
    for r in range(l+1,n+1):
        if L[l-1][0]^L[r][0]==L[r][1]-L[l-1][1]:
            c+=1
print(c+n)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
j=0
c=0
s=a[0]
for i in range(n):
    if j<i:
        j=i
        s=a[i]
    if j<n-1:
        while s&a[j+1]==0:
            s|=a[j+1]
            j+=1
            if j==n-1:
                break
    c+=j-i+1
    s^=a[i]
print(c)