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

import collections

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

c = collections.Counter(x)
li = []
for i in c.values():
    li.append(i)

li.sort(reverse=True)

while li[0] != 1:
    for i in range(len(li)-1):
        if li[i] >= 3:
            li[i] -= 2
        if li[i+1] == 2 and li[i] == 2:
            li[i+1] = 1
            li[i] = 1
    li.sort(reverse=True)
    if len(li) > 1 and li[0] == 2 and li[1] == 1:
        li[0] -= 1
        li.pop(-1)

print(len(li))




### FIXED CODE ###

import collections

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

c = collections.Counter(x)
li = []
for i in c.values():
    li.append(i)

li.sort(reverse=True)

for j in range(2):
    for i in range(len(li) - 1):
        if li[i] >= 3 and li[i] % 2 == 0:
            li[i] = 2
        elif li[i] >= 3 and li[i] % 2 != 0:
            li[i] = 1

        if li[i + 1] == 2 and li[i] == 2:
            li[i + 1] = 1
            li[i] = 1
    li.sort(reverse=True)
    if len(li) > 1 and li[0] == 2 and li[1] == 1:
        li[0] -= 1
        li.pop(-1)


print(len(li))
### BUGGY CODE ###

# coding: utf-8
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N):
    if A[i] % 2 == 0:
        ans += factorization(A[i])[0][1]
print(ans)

### FIXED CODE ###

# coding: utf-8
N = int(input())
A = list(map(int, input().split()))
l = [2**i for i in range(29, -1, -1)]
ans = 0
for i in range(N):
    flag = False
    for j in range(len(l)):
        if A[i] % l[j] == 0 and flag==False:
            ans += 29 - j
            flag = True
print(ans)
### BUGGY CODE ###

import sys

N = int(input())
seats = [None] * (N + 1)


def main():
    print(0)
    answer = input()
    if answer == "Vacant":
        return
    seats[0] = answer == "Male"
    l, r = 0, N
    while l < r:
        # Vacant must be in [l, r).
        assert seats[l] is not None
        q = (l + r) // 2
        #sys.stderr.write(f"l={l} r={r} q={q}\n")
        print(q)
        answer = input()
        if answer == "Vacant":
            return
        seats[q] = answer == "Male"
        if ((q - l) % 2 == 0) ^ (seats[l] == seats[1]):
            r = q
        else:
            l = q
    raise ValueError("something went wrong")


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

N = int(input())
seats = [None] * (N + 1)


def main():
    print(0)
    answer = input()
    if answer == "Vacant":
        return
    seats[0] = answer == "Male"
    l, r = 0, N
    while r - l > 1:
        # Vacant must be in [l, r).
        assert seats[l] is not None
        q = (l + r) // 2
        #sys.stderr.write(f"l={l} r={r} q={q}\n")
        print(q)
        answer = input()
        if answer == "Vacant":
            return
        seats[q] = answer == "Male"
        if ((q - l) % 2 == 0) ^ (seats[l] == seats[q]):
            r = q
        else:
            l = q
    raise ValueError("something went wrong")


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

n = int(input())

connect_list = [ [] for i in range(n) ]
distance_list = [ -1 for i in range(n) ]
color_list = [ "Gray" for i in range(n) ]
distance_list[0] = 0

for i in range(n-1):
	u, v, w = [ int(v) for v in input().split() ]
	w %= 2
	connect_list[u-1].append((v-1,w))
	connect_list[v-1].append((u-1,w))
	

search_list = [0]

while search_list != []:
	s = search_list[0]
	for i in connect_list[s]:
		if distance_list[i[0]] == -1:
			distance_list[i[0]] = (distance_list[s] + i[1]) % 2
			search_list.append(i[0])
	del search_list[0]

for i in distance_list:
	print(i)

### FIXED CODE ###

n = int(input())

connect_list = [ [] for i in range(n) ]
distance_list = [ -1 for i in range(n) ]
color_list = [ "Gray" for i in range(n) ]
distance_list[0] = 0

for i in range(n-1):
	u, v, w = [ int(v) for v in input().split() ]
	w %= 2
	connect_list[u-1].append((v-1,w))
	connect_list[v-1].append((u-1,w))
	

search_list = [0]


while search_list != []:
	s = search_list[0]
	for i in connect_list[s]:
		if distance_list[i[0]] == -1:
			distance_list[i[0]] = (distance_list[s] + i[1]) % 2
			search_list.append(i[0])
	del search_list[0]

for i in distance_list:
	print(i)
### BUGGY CODE ###

N = int(input())
S = []
count = 0
for i in range(N):
    Si = input()
    if Si not in S:
        S.append(Si)
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
    S.append(input())
print(len(set(S)))
### BUGGY CODE ###

import math
k = int(input())
v = 0
for a in range(1, k + 1):
  for b in range(1, k + 1):
    for c in range(1, k + 1):
      v += math.gcd(a, math.gcd(b, c))
print(v)

### FIXED CODE ###

import math
k = int(input())
v = 0
for a in range(1, k + 1):
    for b in range(1, k + 1):
        g = math.gcd(a, b)
        for c in range(1, k + 1):
            v += math.gcd(g, c)
print(v)
### BUGGY CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
MOD = 10**9 + 7

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1 if 1 not in a else 0

a = [i for i in range(2, N+1) if i not in a]
for i in a:
    dp[i] += (dp[i-1] + dp[i-2]) % MOD
print(dp[N] % MOD)

### FIXED CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
MOD = 10**9 + 7
 
dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1 if 1 not in a else 0
 
a = set(list(range(2,N+1))) - set(a)
for i in a:
    dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[N] % MOD)
### BUGGY CODE ###

import numpy as np

def search(now,r,dist,ans):
    if len(r)==0:
        return ans
    min_=float('inf')
    for i,x in enumerate(r):
        if i < len(r)-1:
            min_=min(min_,search(x,r[:i]+r[i+1:],dist,ans+dist[now][x]))
        else:
            min_=min(min_, search(x,r[:i],dist,ans+dist[now][x]))
    return min_

N,M,R=list(map(int,input().split()))
r=list(map(int,input().split()))
r=[x-1 for x in r]
dist=[[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(M):
    A,B,C=list(map(int,input().split()))
    dist[A-1][B-1]=C
    dist[B-1][A-1]=C
for i in range(N):
    dist[i][i]=0
dist=np.array(dist)

ans=float('inf')
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])

ans=float('inf')
for i,x in enumerate(r):
    if i < len(r)-1:
        ans=min(ans, search(x,r[:i]+r[i+1:],dist,0))
    else:
        ans=min(ans, search(x,r[:i],dist,0))
if ans==float('inf'):
    print(0)
else:
    print(int(ans))

### FIXED CODE ###

from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall as ws

def search(r,dist,ans):
    sum_=0
    for i in range(1,len(r)):
        sum_+=dist[r[i-1]][r[i]]
    return sum_

N,M,R=list(map(int,input().split()))
r=list(map(int,input().split()))
r=[x-1 for x in r]
dist=[[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(M):
    A,B,C=list(map(int,input().split()))
    dist[A-1][B-1]=C
    dist[B-1][A-1]=C
for i in range(N):
    dist[i][i]=0
dist=ws(dist)

ans=float('inf')

ans=float('inf')
r=permutations(r)
for x in r:
    ans=min(ans,search(x,dist,0))
print(int(ans))
### BUGGY CODE ###

N=int(input())
ls=[]
n=0
for i in range(N):
    str1=''.join(sorted(input()))
    n+=ls.count(str1)
    ls.append(str1)
print(n)        


### FIXED CODE ###

N=int(input())
dic={}
ans=0
for i in range(N):
    str1=''.join(sorted(input()))
    n=len(str1)
    if n in dic:
        if str1 in dic[n]:
            ans+=dic[n][str1]
            dic[n][str1]+=1
        else:
            dic[n][str1]=1
    else:
        dic[n]={str1:1}
    
print(ans)
### BUGGY CODE ###

import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=[int(input()) for i in range(n-1)]
# print(a)
dic=defaultdict(list)
for i in range(n-1):
    p=a[i]
    dic[p].append(i+2)
# print(dic)

lst=[-1]*(n+1)

def solve(m):
    if lst[m]!=-1:
        return lst[m]
    tmp=[]
    for i in dic[m]:
        tmp.append(solve(i))
    tmp.sort(reverse=True)
    rtn=0
    for i in range(len(tmp)):
        rtn=max(rtn,tmp[i]+i+1)
    lst[m]=rtn
    return rtn

solve(1)
# print(lst)
print(max(lst))

### FIXED CODE ###

import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

def main():
    n=int(input())
    a=[int(input()) for i in range(n-1)]
    # print(a)
    dic={}
    for i in range(n-1):
        p=a[i]
        if p in dic:
            dic[p].append(i+2)
        else:
            dic[p]=[i+2]


    lst=[-1]*(n+1)

    def solve(m):
        if lst[m]!=-1:
            return lst[m]
        tmp=[]
        if m in dic:

            for i in dic[m]:
                tmp.append(solve(i))
        tmp.sort(reverse=True)
        rtn=0
        for i in range(len(tmp)):
            rtn=max(rtn,tmp[i]+i+1)
        lst[m]=rtn
        return rtn

    solve(1)
    # print(lst)
    print(max(lst))
main()
### BUGGY CODE ###

S = input()
S = S[::-1]
N = len(S)

mod = 10**9 + 7
R = []
digit = 1
while True:
  r = [i*digit % 13 for i in range(10)]
  if r in R:
    break
  else:
    R.append(r)
  
  digit = digit*10 % 13


nr = len(R)
dp = [[1] + [0]*12] + [[0]*13 for i in range(N)]
for i, s in enumerate(S):
  if s == '?':
    _R = R[i%nr]
    for j in range(13):
      for r in _R:
        dp[i+1][(j+r)%13] = (dp[i+1][(j+r)%13] + dp[i][j]) % mod
      
  else:
    s = int(s)
    r = s*10**i % 13
    dp[i+1] = dp[i][-r:] + dp[i][:-r]

print(dp[-1][5])

### FIXED CODE ###

S = input()
S = S[::-1]
N = len(S)

mod = 10**9 + 7

dp = [[1] + [0]*12] + [[0]*13 for i in range(N)]

digit = 1
for i, s in enumerate(S):
  if s == '?':
    R = [j*digit % 13 for j in range(10)]
    for j in range(13):
      for r in R:
        dp[i+1][(j+r)%13] = (dp[i+1][(j+r)%13] + dp[i][j]) % mod
      
  else:
    s = int(s)
    r = s*digit % 13
    dp[i+1] = dp[i][-r:] + dp[i][:-r]
  
  digit *= 10
  digit %= 13

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

N=int(input())
*A,=map(int,input().split())
S=[sum(map(lambda x : abs(x-a) if abs(x-a)==1 else 0,A)) for a in A]
print(max(S)+1)

### FIXED CODE ###

input()
*A,=map(int,input().split())
D=[0]*(10**7)

for a in A:
    D[a-1]+=1
    D[a]+=1
    D[a+1]+=1
print(max(D))
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(N + 1):
    for g in range(N + 1):
        if (N - (R * r) - (G * g)) % B == 0 and 0 <= ((N - (R * r) - (G * g)) // B) <= 3000:
            ans += 1
print (ans)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(N + 1):
    for g in range(N + 1):
        if (N - (R * r) - (G * g)) % B == 0 and 0 <= ((N - (R * r) - (G * g)) // B) <= 3000:
            ans += 1
print (ans)
### BUGGY CODE ###

import sys

INF = 10 ** 18
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict


def li():
    return [int(x) for x in input().split()]


from collections import deque

H, W = li()
Ch, Cw = li()
Dh, Dw = li()
S = [list(input()) for x in range(H)]

v = [(1, 0), (0, 1), (-1, 0), (0, -1)]


def bfs():
    costmap = defaultdict(lambda: -1)
    costmap[Cw, Ch] = 0
    que = deque([])
    que.append((Cw, Ch))

    while que:
        # print(que)
        # 左から取り出す
        x, y = que.popleft()
        # 通常移動パターン
        for i in range(len(v)):
            nx = x + v[i][0]
            ny = y + v[i][1]
            # バリデーション
            if nx <= 0 or nx > W or ny <= 0 or ny > H:
                continue
            if S[ny - 1][nx - 1] != '.':
                continue
            # 初探索 or コストが下がる場合
            if costmap[nx, ny] == -1 or costmap[x, y] < costmap[nx, ny]:
                # コストゼロは左から
                que.appendleft((nx, ny))
                costmap[nx, ny] = costmap[x, y]
        # 特殊移動パターン
        for i in range(x - 2, x + 3):
            for j in range(y - 2, y + 3):
                nx, ny = i, j
                # バリデーション
                if nx <= 0 or nx > W or ny <= 0 or ny > H:
                    continue
                if S[ny - 1][nx - 1] != '.':
                    continue
                # 初探索 or コストが下がる場合
                if costmap[nx, ny] == -1 or costmap[x, y] + 1 < costmap[nx, ny]:
                    # コスト1は右から
                    que.append((nx, ny))
                    costmap[nx, ny] = costmap[x, y] + 1
    return costmap


costmap = bfs()
# print(costmap)
print(costmap[Dw, Dh])

### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
s=[list(input()) for i in range(h)]
 
#幅優先で解く。
dx=[1,0,-1,0]
dy=[0,1,0,-1]
def bfs():
  maze=[[-1]*w for i in range(h)]
  maze[ch-1][cw-1]=0
  qu=deque([])
  qu.append((cw-1,ch-1))
  magic=0
  
  while qu:
    x,y=qu.popleft()
    for i in range(4):
      nx=dx[i]+x
      ny=dy[i]+y
      if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]):
        qu.appendleft((nx,ny))
        maze[ny][nx]=maze[y][x]
    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        nx=i
        ny=j
        if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]+1):
          qu.append((nx,ny))
          maze[ny][nx]=maze[y][x]+1
  return maze
    
maze = bfs()
print(maze[dh-1][dw-1])
### BUGGY CODE ###

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

for j in t:
  if j != sorted(t)[n-1]:
  	print(sorted(t)[n-1])
  else:
    print(sorted(t)[n-2])

### FIXED CODE ###

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

ma = max(t)
ma2 = sorted(t)[n-2]

for j in t:
  if j != ma:
  	print(ma)
  else:
    print(ma2)
### BUGGY CODE ###

def main():
    n, m, q = map(int, input().split())
    trains = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for _ in range(m):
        l, r = map(int, input().split())
        trains[l][r] += 1
    for i in range(n + 1):
        for j in range(1, n + 1):
            trains[i][j] += trains[i][j - 1]
    for _ in range(q):
        p, q = map(int, input().split())
        ans = 0
        for i in range(p, q + 1):
            ans += trains[i][q] - trains[i][p - 1]
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, m, q = map(int, input().split())
    trains = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for _ in range(m):
        l, r = map(int, input().split())
        trains[l][r] += 1
    for i in range(n + 1):
        for j in range(1, n + 1):
            trains[i][j] += trains[i][j - 1]
    for _ in range(q):
        p, q = map(int, input().split())
        ans = 0
        for i in range(p, q + 1):
            ans += trains[i][q] - trains[i][p - 1]
        print(ans)


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

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


bit= [[0]*60 for i in range(n)]
for i in range(n):
    a=A[i]
    j=1
    if a!=0:    
        while a//2>0:
            if a%2==1:
                bit[i][60-j]=1
                j+=1
                a=a//2
            else:
                j+=1
                a=a//2
        bit[i][60-j]=1
      
xor=[0]*60
    
for j in range(60):
    l=0
    for i in range(n):
        l+=bit[i][j]
    xor[j]=l*(n-l)
    
L=10**9+7
ans=xor[0]
for j in range(60-1):
    ans=((2*ans)+xor[j+1])%L
print(ans)    

### FIXED CODE ###

def main():
    """"ここに今までのコード"""
 
n = int(input())
A = [int(a) for a in input().split()]
mod=10**9+7
 
ans=0
for i in range(60):
    l=sum([a%2 for a in A])
    ans=(ans+l*(n-l)*(2**i))%mod
    A=[a//2 for a in A]
    
 
#ans=xor[0]
#for j in range(60-1):
#    ans=((2*ans)+xor[j+1])%mod
print(int(ans)) 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
array = []
for i in range(n+1):
    if (str(i).count('7') + str(i).count('5') + str(i).count('3')) == len(str(i)):
        if '7' in str(i):
            if '5' in str(i):
                if '3' in str(i):
                    array.append(i)
print(len(array))


### FIXED CODE ###

n = int(input())
def dfs(s):
        if int(s) > n:
                return 0
        ret = 0
        if s.count('7')>0 and s.count('5')>0 and s.count('3')>0:
            ret = 1
        for c in '753':
                ret += dfs(s + c)
        return ret
print(dfs('0'))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections import Counter
INF = float("inf")

MOD = 1000000007  # type: int


def cmb(n, r):
    r = min(r, n-r)
    if r < 0 or r > n:
        return 0
    if r == 0:
        return 1
    if r == 1:
        return n

    numer = [n - r + k + 1 for k in range(r)]
    denom = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denom[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numer[k - offset] /= pivot
                denom[k] /= pivot

    result = 1
    for k in range(r):
        if numer[k] > 1:
            result *= int(numer[k])

    return result


def solve(n: int, a: "List[int]"):
    (m, _), = Counter(a).most_common(1)
    left = a.index(m)
    right = a.index(m, left+1)
    for i in range(1, n+2):
        print((cmb(n+1, i)-cmb(n-right+left, i-1)) % MOD)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(n+1)]  # type: "List[int]"
    solve(n, a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import Counter
INF = float("inf")

MOD = 1000000007  # type: int


class Combination(object):
    def __init__(self, N, mod):
        self.N = N
        self.MOD = mod
        self.fac = [0] * (N+1)
        self.finv = [0] * (N+1)
        self.inv = [0] * (N+1)
        self.cmb_init()

    def cmb_init(self):
        self.fac[0] = 1
        self.fac[1] = 1
        self.finv[0] = 1
        self.finv[1] = 1
        self.inv[1] = 1
        for i in range(2, self.N+1):
            self.fac[i] = self.fac[i-1]*i % self.MOD
            self.inv[i] = -self.inv[self.MOD % i]*(self.MOD//i) % self.MOD
            self.finv[i] = self.finv[i-1]*self.inv[i] % self.MOD

    def __call__(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return self.fac[n] * (self.finv[k]*self.finv[n-k] % self.MOD) % self.MOD


def solve(n: int, a: "List[int]"):
    (m, _), = Counter(a).most_common(1)
    left = a.index(m)
    right = a.index(m, left+1)
    cmb = Combination(n+1, MOD)
    for i in range(1, n+2):
        print((cmb(n+1, i)-cmb(n-right+left, i-1)) % MOD)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(n+1)]  # type: "List[int]"
    solve(n, a)


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

n, k = map(int, input().split())
l = list(map(int, input().split()))
 
tmp = l[:k]
now = sum(tmp)
 
for i in range(n-k):
  tmp.pop(0)
  tmp.append(l[i+k])
  now = max(sum(tmp), now)
  
print((now + k) / 2)

### FIXED CODE ###

n, k = map(int, input().split())
l = list(map(int, input().split()))
 
tmp = sum(l[:k])
now = tmp
 
for i in range(n-k):
  tmp -= l[i]
  tmp += l[i+k]
  now = max(tmp, now)
  
print((now + k) / 2)
### BUGGY CODE ###

from collections import deque

H, W = map(int, list(input().split()))
Ch, Cw = map(int, list(input().split()))
Ch -= 1
Cw -= 1
Dh, Dw = map(int, list(input().split()))
Dh -= 1
Dw -= 1
S = [list(input()) for _ in range(H)]

dh = [-1, 0, 0, 1]
dw = [0, 1, -1, 0]

INF = pow(10, 10)
seen = [[INF] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append([Ch, Cw, 0])

while q:
    th, tw, t = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1:
            continue
        if S[nh][nw] == '#':
            continue
        if seen[nh][nw] <= t:
            continue
        seen[nh][nw] = t
        q.append([nh, nw, t])
    for dh2 in range(-2, 3):
        for dw2 in range(-2, 3):
            if dh2 == 0 and dw2 == 0:
                continue
            nh = th + dh2
            nw = tw + dw2
            if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1:
                continue
            if S[nh][nw] == '#':
                continue
            if seen[nh][nw] <= t + 1:
                continue
            seen[nh][nw] = t + 1
            q.append([nh, nw, t + 1])

if seen[Dh][Dw] is INF:
    print(-1)
else:
    print(seen[Dh][Dw])


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh, Dw = map(int, input().split())
Dh -= 1
Dw -= 1
S = [input() for _ in range(H)]

dh = [-1, 0, 0, 1]
dw = [0, 1, -1, 0]

INF = pow(10, 10)
seen = [[INF] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append([Ch, Cw])

while q:
    th, tw = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= seen[th][tw]:
            continue
        seen[nh][nw] = seen[th][tw]
        q.append([nh, nw])
    for dh2 in range(-2, 3):
        for dw2 in range(-2, 3):
            if dh2 == 0 and dw2 == 0:
                continue
            nh = th + dh2
            nw = tw + dw2
            if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= seen[th][tw] + 1:
                continue
            seen[nh][nw] = seen[th][tw] + 1
            q.appendleft([nh, nw])

if seen[Dh][Dw] is INF:
    print(-1)
else:
    print(seen[Dh][Dw])
### BUGGY CODE ###

def main():
    from fractions import gcd
    import sys
    input=sys.stdin.readline
    N=int(input())
    A=list(map(int,input().split()))
    lcm=A[0]
    for a in A:
        lcm=lcm*a//(gcd(lcm,a))

    ans=0
    for a in A:
        ans=ans+(lcm//a)
    print(ans%(10**9+7))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from fractions import gcd
    import sys
    input=sys.stdin.readline
    N=int(input())
    A=list(map(int,input().split()))
    lcm=A[0]
    for a in A:
        lcm=lcm*a//(gcd(lcm,a))

    ans=0
    for a in A:
        ans=ans+(lcm//a)
    print(ans%(10**9+7))

if __name__ == '__main__':
    main()