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

import sys
sys.setrecursionlimit(10**7)
import math
mod = 10**9 + 7
def I(): return int(input())
def II(): return map(int, input().split())
def L(): return list(map(int, input().split()))
def TWO(M):
  L=[0]*M
  R=[0]*M
  for i in range(M):
    L[i],R[i] = II()
  return L, R

N = I()
A = [0]*N
for i in range(N):
  A[i] = I()

check = [0]*N
counter = 0
all_counter = 0
while 1:
  temp = -1
  for i in range(N):
    if check[i]==0 and temp<A[i]:
      check[i]=1
      temp = A[i]
      all_counter += 1
  counter += 1
  if all_counter==N:
    break
  
print(counter)

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

from bisect import bisect_left

N = I()
A = [0]*N
for i in range(N):
    A[i] = I()

val = [-1]*N
for i in range(N):
    temp = bisect_left(val,A[i])
    val[temp-1] = A[i]

ans = 0
for i in range(N):
    if val[i]!=-1:
        ans += 1

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

h,n=map(int,input().split())
ans=[10**10 for i in range(h+1)]+[0 for i in range(10**4)]
ans[0]=0
for i in range(n):
    a,b=map(int,input().split())
    tmp=0
    while tmp<=h:
        ans[tmp]=min(ans[tmp-a]+b,ans[tmp])
        tmp+=1
print(ans[h])

### FIXED CODE ###

h,n=map(int,input().split())
ans=[10**10 for i in range(h+1)]+[0 for i in range(10**4)]
ans[0]=0
for i in range(n):
    a,b=map(int,input().split())
    tmp=0
    while tmp<=h:
        ans[tmp]=min(ans[tmp-a]+b,ans[tmp])
        tmp+=1
print(ans[h])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

def dfs(G, p, pre, t, edge, x):
    for nxt in G[p]:
        if nxt == pre:
            continue
        a, b = p, nxt
        if b < a:
            a, b = b, a
        if nxt == t:
            edge[(a, b)] += x
            return True
        if dfs(G, nxt, p, t, edge, x):
            edge[(a, b)] += x
            return True
    return False

def main():
    n = int(input())
    G = [[] for _ in range(n)]
    edge = {}
    for _ in range(n-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        G[a].append(b)
        G[b].append(a)
        if b < a:
            a, b = b, a
        edge[(a, b)] = 0
    m = int(input())
    for i in range(m):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        x = 1<<i
        dfs(G, u, -1, v, edge, x)
    ans = 2**(n-1)
    for i in range(1, 2**m):
        bit_cnt = 0
        for j in range(m):
            if (i & (1<<j)) != 0:
                bit_cnt += 1
        cnt = 0
        for v in edge.values():
            if (v & i) != 0:
                cnt += 1
        x = 2**(n-1 - cnt)
        if bit_cnt % 2 == 0:
            ans += x
        else:
            ans -= x
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

def dfs(G, p, pre, t, edge, x):
    for nxt in G[p]:
        if nxt == pre:
            continue
        a, b = p, nxt
        if b < a:
            a, b = b, a
        if nxt == t:
            edge[(a, b)] += x
            return True
        if dfs(G, nxt, p, t, edge, x):
            edge[(a, b)] += x
            return True
    return False

def main():
    n = int(input())
    G = [[] for _ in range(n)]
    edge = {}
    for _ in range(n-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        G[a].append(b)
        G[b].append(a)
        if b < a:
            a, b = b, a
        edge[(a, b)] = 0
    m = int(input())
    for i in range(m):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        x = 1<<i
        dfs(G, u, -1, v, edge, x)
    ans = 2**(n-1)
    for i in range(1, 2**m):
        bit_cnt = 0
        for j in range(m):
            if (i & (1<<j)) != 0:
                bit_cnt += 1
        cnt = 0
        for v in edge.values():
            if (v & i) != 0:
                cnt += 1
        x = 2**(n-1 - cnt)
        if bit_cnt % 2 == 0:
            ans += x
        else:
            ans -= x
    print(ans)

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

# coding: utf-8
# Your code here!
MOD=10**9+7
n=int(input())
A= [[int(i) for i in input().split()] for j in range(n)]

dp = [[0]*(2**n) for i in range(n+1)]
dp[0][0] = 1
for m in range(1,n+1):
    for a in range(2**n):
        dp[m][a] = sum(dp[m-1][a-2**c] for c in range(n) if 2**c&a != 0 and A[m-1][c]==1)%MOD


print(dp[n][2**n-1])

### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline

def itercomb(n,k):
    _a = (1<<k)-1
    yield _a
    while 1:
        _x = _a & -_a
        _y = _a + _x
        _a = (((_a & ~_y) // _x) >> 1) | _y
        if _a >= _ALL: break
        yield _a

n=int(input())
A= [[int(i) for i in input().split()] for j in range(n)]

MOD=10**9+7
_ALL=1<<n
dp = [0]*(_ALL)
dp[0] = 1

for m in range(1,n+1):
    for a in itercomb(n,m):
        for c,i in enumerate(A[m-1]):
            if (1<<c)&a and i:
                dp[a] += dp[a^(1<<c)]
                if dp[a] > MOD:
                    dp[a] -= MOD


#print(dp)
print(dp[2**n-1])
### BUGGY CODE ###

from sys import stdin


def get_result(data):
    # N = int(data[0][0])
    S = data[1][0]
    r_index = [i for i in range(len(S)) if S[i] == 'R']
    g_index = [i for i in range(len(S)) if S[i] == 'G']
    b_index = [i for i in range(len(S)) if S[i] == 'B']
    all_case = len(r_index) * len(g_index) * len(b_index)
    invalid_case = 0
    for i in r_index:
        for j in g_index:
            s_i, s_j = sorted([i, j])
            tmp_max_b = s_j + (s_j-s_i)
            if tmp_max_b in b_index:
                invalid_case += 1
            tmp_min_b = s_i - (s_j-s_i)
            if tmp_min_b in b_index:
                invalid_case += 1
            tmp_mid_b = (s_i + s_j) / 2
            if tmp_mid_b in b_index:
                invalid_case += 1
    return all_case - invalid_case


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(str, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)


### FIXED CODE ###

from sys import stdin


def get_result(data):
    # N = int(data[0][0])
    S = data[1][0]
    r_index = [i for i in range(len(S)) if S[i] == 'R']
    g_index = [i for i in range(len(S)) if S[i] == 'G']
    b_index = set([i for i in range(len(S)) if S[i] == 'B'])
    all_case = len(r_index) * len(g_index) * len(b_index)
    invalid_case = 0
    for i in r_index:
        for j in g_index:
            s_i, s_j = sorted([i, j])
            tmp_max_b = s_j + (s_j-s_i)
            if tmp_max_b in b_index:
                invalid_case += 1
            tmp_min_b = s_i - (s_j-s_i)
            if tmp_min_b in b_index:
                invalid_case += 1
            tmp_mid_b = (s_i + s_j) / 2
            if tmp_mid_b in b_index:
                invalid_case += 1
    return all_case - invalid_case


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(str, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)
### BUGGY CODE ###

import itertools
d,g=map(int,input().split())
p=[]
c=[]
for i in range(d):
    p1,c1=map(int,input().split())
    p.append(p1)
    c.append(c1//100)
n=list(itertools.permutations(list(range(1,d+1))))
ans=3000
g//=100
for i in range(len(n)):
    cnt=g
    cnt2=0
    for j in range(d):
        num3=n[i][j]
        num5=p[num3-1]
        num4=num3*num5
        if num4>=cnt:
            cnt2+=((cnt-1)//num3)+1
            break
        elif num4+c[num3-1]>=cnt:
            cnt2+=num5
            break
        else:
            cnt-=num4+c[num3-1]
            cnt2+=num5
    ans=min(ans,cnt2)
print(ans)


### FIXED CODE ###

import itertools
d,g=map(int,input().split())
p=[]
c=[]
for i in range(d):
    p1,c1=map(int,input().split())
    p.append(p1)
    c.append(c1//100)
n=list(itertools.permutations(list(range(1,d+1))))
ans=1024
g//=100
for i in range(len(n)):
    cnt=g
    cnt2=0
    for j in range(d):
        num3=n[i][j]
        num4=num3*p[num3-1]
        if num4>=cnt:
            cnt2+=((cnt-1)//num3)+1
            break
        elif num4+c[num3-1]>=cnt:
            cnt2+=p[num3-1]
            break
        else:
            cnt-=num4+c[num3-1]
            cnt2+=p[num3-1]
    ans=min(ans,cnt2)
print(ans)
### BUGGY CODE ###


n=int(input())
S=[]
S=input().split()
q=int(input())
T=[]
T=input().split()
point=0
for i in range(q):	
	for j in range(n):
		if T[i]==S[j]:
			point+=1
			break
			
print(point)


### FIXED CODE ###

#16D8101014F 久留米 竜之介 2018/5/14
n=int(input())
S=list(map(int,input().split()))
q=int(input())
T=list(map(int,input().split()))
point=0
for i in T:
	left=0
	right=n
	while left < right:
		mid=int((left+right)/2)
		if S[mid] == i:
			point += 1
			break
		elif i < S[mid]:
			right = mid
		else:
			left = mid + 1
	#print(i,point)

print(point)
### BUGGY CODE ###

N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(K)]

D = [1]
M = 5000
memo = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      ll = i - min(i, r)
      rr = i - l + 1
      LL = (ll + M - 1) // M
      RR = rr // M
      if RR > LL:
        count += sum(D[ll:LL*M]) + sum(memo[LL:RR]) + sum(D[RR*M:rr])
      else:
        count += sum(D[ll:rr])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
print(D[-1])

### FIXED CODE ###

N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(K)]

D = [1]
M = 100
memo = []
memo2 = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      l1 = i - min(i, r)
      r1 = i - l + 1
      l2 = (l1 + M - 1) // M
      r2 = r1 // M
      l3 = (l2 + M - 1) // M
      r3 = r2 // M
      if r3 > l3:
        count += sum(D[l1:l2*M]) + sum(memo[l2:l3*M]) + sum(memo2[l3:r3]) + sum(memo[r3*M:r2]) + sum(D[r2*M:r1])
      elif r2 > l2:
        count += sum(D[l1:l2*M]) + sum(memo[l2:r2]) + sum(D[r2*M:r1])
      else:
        count += sum(D[l1:r1])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
    if len(memo) % M == 0:
      memo2.append(sum(memo[-M:]))
print(D[-1])
### BUGGY CODE ###

D, G = map(int, input().split())

Score = []
q_sum = 0
for i in range(D):
    p, c = map(int, input().split())
    q_sum += p
    Score.append([(i+1)*100, p, c])

def Calc(score, num):
    temp = list(filter(lambda x: x[1] < num+1, score))
    if temp == []:
        return score[-1][0] * num
    else:
        cand = []
        if len(score) == 1:
            cand.append(temp[0][0]*temp[0][1] + temp[0][2])
        else:
            copy_score = score.copy()
            for t in temp:
                temp_score = score.copy()
                del temp_score[temp_score.index(t)]
                del copy_score[copy_score.index(t)]
                cand.append(t[0]*t[1] + t[2] + Calc(temp_score, num - t[1]))
            if len(copy_score) > 0:
                cand.append(copy_score[-1][0] * num)
        return max(cand)

a, b = 1, q_sum+1
while (b-a) > 1:
    if Calc(Score, (b+a) // 2) >= G:
        b = (b+a) // 2
    else:
        a = (b+a) // 2
if Calc(Score, a) >= G:
    print(a)
else:
    print(b)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import math

s_in = lambda: stdin.readline()[:-1] # s = s_in()
d_in = lambda: int(stdin.readline()) # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split())) # List = ds_in()

D, G = ds_in()

Score = []
for i in range(D):
    p, c = ds_in()
    Score.append([(i+1)*100, p, c])

INF = 10**10

search = []
def SearchMin(search, idx):
    if idx == D:
        score = 0
        num = 0
        res = []
        maxprob = [0, 0, 0]
        for s, i in zip(Score, search):
            num += s[1] * i
            score += (s[0] * s[1] + s[2]) * i
            if i == 0 and s[0] > maxprob[0]:
                maxprob = s.copy()
        if (G > score) and (math.ceil((G - score) / maxprob[0]) <= maxprob[1]):
            return num + max(0, math.ceil((G - score) / maxprob[0]))
        elif G <= score:
            return num
        else:
            return INF

    else:
        s0 = search.copy()
        s0.append(0)
        s1 = search.copy()
        s1.append(1)
        idx += 1
        ans0 = SearchMin(s0, idx)
        ans1 = SearchMin(s1, idx)
        return min(ans0, ans1)

print(SearchMin(search, 0))
### BUGGY CODE ###

import math
from functools import reduce

n = int(input())
ans = 0

for i in range(1, n+1, 1):
    for j in range(1, n+1, 1):
        for k in range(1, n+1, 1):
            ans += reduce(math.gcd, (i, j, k))

print(ans)

### FIXED CODE ###

# gcdをmathからimport
from math import gcd
n = int(input())
ans = 0

for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            # gcd(i,j)とkのgcdを計算
            # 1番小さい数字が制限になる
            ans += gcd(gcd(i, j), k)
 
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

N = int(input())
A = input().split(" ")
result = 1
if "0" in A:
  print(0)
  exit()
else:
  for i in range(N):
    result *= int(A[i])
    if result > 10**18:
      print(-1)
      exit()
print(result)
### BUGGY CODE ###

d1 = {}
def popcount(n):
    if n not in d1:
        q = n
        s = 0
        while q > 0:
            q, r = divmod(q, 2)
            s += r
        d1[n] = s
    return d1[n]

d2 = {}
def f(n):
    X = [n]
    c = 0
    while n != 0:
        if n in d2:
            k = d2[n]
            break
        n %= popcount(n)
        c += 1
        X.append(n)
    else:
        k = 0
    d2.update({x:i+k for i, x in enumerate(X[::-1])})
    return c + k

n, X = open(0).read().split()
n = int(n)
x = int(X, 2)
X = list(map(int, X))
c = popcount(x)
for i in range(n):
    if X[i]:
        y = x - 2**(n-i-1)
        t = c-1
    else:
        y = x + 2**(n-i-1)
        t = c+1
    if y != 0:
        print(f(y%t) + 1)
    else:
        print(0)

### FIXED CODE ###

n, X = open(0).read().split()
n = int(n)
x = int(X, 2)
X = list(map(int, X))

def popcount(n):
    return bin(n).count('1')

ma = 2 * 10**5 + 1
dp = [0] * ma
for i in range(1, ma):
    dp[i] = dp[i % popcount(i)] + 1

c = popcount(x)
a = x % (c+1)
if c == 1:
    for i in range(n):
        if X[i]:
            print(0)
        else:
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)
else:
    b = x % (c-1)
    for i in range(n):
        if X[i]:
            print(dp[(b - pow(2, n-i-1, c-1)) % (c-1)] + 1)
        else:
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)
### BUGGY CODE ###

import sys
n, p = [int(i) for i in sys.stdin.readline().split()]
s = input()
memo_ls = [{i : 0 for i in range(p)} for j in range(n)]
memo_ls[0][int(s[0]) % p] = 1
for i, _s in enumerate(s[1:], 1):
    _s = int(_s)
    memo_ls[i][_s % p] += 1
    for k, v in memo_ls[i-1].items():
        if v == 0:
            continue
        memo_ls[i][(k * 10 + _s) % p] += v
print(sum([memo_ls[i][0] for i in range(n)]))

### FIXED CODE ###

import sys
from collections import Counter
n, p = [int(i) for i in sys.stdin.readline().split()]
s = sys.stdin.readline().strip()
if p == 2:
    ans = 0
    for i, _s in enumerate(s, 1):
        if int(_s) % 2 == 0:
            ans += i
    print(ans)
elif p == 5:
    ans = 0
    for i, _s in enumerate(s, 1):
        if int(_s) in {0, 5}:
            ans += i
    print(ans)
else:
    us = Counter([])
    cur = ""
    ans = 0
    mod = 0
    keta_mod = 1
    for i, _s in enumerate(s[::-1]):
        keta_mod = keta_mod * 10 % p
        mod = (keta_mod * int(_s) + mod) % p
        if mod == 0:
            ans += us[mod] + 1
        else:
            ans += us[mod]
        us.update([mod])
    print(ans)
### BUGGY CODE ###

h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]

dp = [10 ** 20] * 10 ** 5
dp[0] = 0
for a, b in ab:
    for i in range(h):
        dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))

### FIXED CODE ###

h, n = map(int, input().split())
ab = tuple(tuple(map(int, input().split())) for _ in range(n))

dp = [10 ** 20] * 10 ** 4 * 2
dp[0] = 0
for a, b in ab:
    for i in range(h):
        dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))
### BUGGY CODE ###

import heapq

n,m,s=map(int,input().split())
path=[[] for _ in range(n+1)]
coin=[(0,0)]
time=[float("inf") for _ in range(n+1)]
time[0]=0
queue=[]
for i in range(m):
    u,v,a,b=map(int,input().split())
    path[u].append((v,a,b))
    path[v].append((u,a,b))

for i in range(n):
    c,d=map(int,input().split())
    coin.append((c,d))

heapq.heappush(queue,(0,s,1))
while len(queue)!=0:
    t,c,v=heapq.heappop(queue)
    if time[v]>t:
        time[v]=t
    for nv,na,nb in path[v]:
        if na>c:
            continue
        else:
            heapq.heappush(queue,(t+nb,c-na,nv))
    if c > n*50:
        continue
    else:
        heapq.heappush(queue,(t+coin[v][1],c+coin[v][0],v))
    
print(*time[2:],sep="\n")

### FIXED CODE ###

import heapq

n,m,s=map(int,input().split())
limit=2500
s=min(s,limit)
path=[[] for _ in range(n+1)]
coin=[(0,0)]
time=[[float("inf") for _ in range(limit+1)] for _ in range(n+1)]
queue=[]

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

for i in range(n):
    c,d=map(int,input().split())
    coin.append((c,d))

time[1][s]=0
heapq.heappush(queue,(0,1,s))

while len(queue)!=0:
    t,v,c=heapq.heappop(queue)
    for nv,na,nb in path[v]:
        if na>c:
            continue
        elif time[nv][c-na]<=t+nb:
            continue
        else:
            time[nv][c-na]=t+nb
            heapq.heappush(queue,(t+nb,nv,c-na))

    nc=min(c+coin[v][0],limit)
    nt=t+coin[v][1]
    if time[v][nc]<=nt:
        continue
    else:
        time[v][nc]=nt
        heapq.heappush(queue,(nt,v,nc))
    
for i in range(2,n+1):
    print(min(time[i]))
### BUGGY CODE ###

# ABC103D_IslandsWar.py

import operator

"""
区画スケジューリング
まず、(ai, bi) の組を bi について昇順にソートします。ソートした順に、以下を行う。
• 既にその要望を満たしている場合、何もしない。
• 要望を満たしていない場合、bi − 1 番目の島と bi 番目の島を接続する橋を取り除く。
TLE に注意
"""

n, m = map(int, input().split())
ms = [tuple(map(int, input().split())) for i in range(m)]
bridges = set()
ms2 = sorted(ms, key=operator.itemgetter(1))

for i in range(m):
    if any(x in bridges for x in range(ms2[i][0], ms2[i][1])):
        pass
    else:
        bridges.add(ms2[i][1]-1)

if __name__ == "__main__":
    print(len(bridges))


### FIXED CODE ###

# ABC103D_IslandsWar.py

import operator

"""
区画スケジューリング
まず、(ai, bi) の組を bi について昇順にソートします。ソートした順に、以下を行う。
• 既にその要望を満たしている場合、何もしない。
• 要望を満たしていない場合、bi − 1 番目の島と bi 番目の島を接続する橋を取り除く。
TLE に注意
"""

n, m = map(int, input().split())
bridges = [0]
ms = sorted((tuple(map(int, input().split())) for i in range(m)), key=operator.itemgetter(1))

for i in range(m):
    if ms[i][0] <= bridges[-1]:
        pass
    else:
        bridges.append(ms[i][1] - 1)

if __name__ == "__main__":
    print(len(bridges)-1)
### BUGGY CODE ###

def s(n):
    if n<10:
        return n
    else:
        return n%10+s(n//10)

k =int(input())
n=0
for _ in [0]*k:
    n +=1    
    minn = n
    d = 10
    while n>=d:
        m = (n//d+1)*d-1
        if minn*s(m)>m*s(minn):
            minn = m
    n = minn
    print(n)


### FIXED CODE ###

def s(n):
    if n<10:
        return n
    else:
        return n%10+s(n//10)
n=0
for _ in [0]*int(input()):
    n +=1    
    minn = n
    d = 1
    while n>=d:
        d *= 10    
        m = (n//d+1)*d-1
        if minn*s(m)>m*s(minn):
            minn = m
    n = minn
    print(n)
### BUGGY CODE ###

s = input()
q = int(input())

query = [""]*q
t = [0]*q
f = [0]*q
c = [""]*q

for i in range(q):
    query[i] = input()
    if query[i]=="1":
        t[i] = 1
    else:
        r = query[i].split()
        t[i] = 2
        f[i] = int(r[1])
        c[i] = r[2]

for i in range(q):
    if t[i]==1:
        s = s[::-1]
    elif t[i]==2:
        if f[i]==1:
            s = c[i]+s
        elif t[i]==2:
            s = s+c[i]
print(s)

### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())

query = []
rev=1

for i in range(q):
    query.append(input().split())

for i in range(q):
    if query[i][0]=="1":
        rev*=-1
    else:
        if rev==1:
            if query[i][1]=="1":
                s.appendleft(query[i][2])
            else:
                s.append(query[i][2])
        else:
            if query[i][1]=="2":
                s.appendleft(query[i][2])
            else:
                s.append(query[i][2])

result="".join(list(s))
if rev==-1:
    result = result[::-1]
print(result)
### BUGGY CODE ###

n, a, b = map(int, input().split())
tmp = []
while len(tmp) <= n:
  for i in range(a):
    tmp.append('b')
  for j in range(b):
    tmp.append('r')
ans = []
for k in range(n):
  ans.append(tmp[k])
print(ans.count('b'))


### FIXED CODE ###

n, a, b = map(int, input().split())
q = n // (a+b)
mod = n % (a+b)
ans = q * a
if (mod > a):
  ans += a
else:
  ans += mod
print(ans)
### BUGGY CODE ###

N,M=map( int, input().split())
A=list( map( int, input().split()))
A.sort(reverse=True)
for i in range(M):
    A[A.index(max(A))] = int(A[A.index(max(A))]/2)
print(sum(A))

### FIXED CODE ###

import heapq
def main():
    N,M=map( int, input().split())
    A=list( map( int, input().split()))
    A = list(map(lambda x: x*(-1), A))
    heapq.heapify(A)
    for _ in range(M):
        u = heapq.heappop(A)
        heapq.heappush(A,int(u/2))
    print(-sum(A))


    

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

str_list = str(input())
length = len(str_list)
 
cnt = 4
result = 0
 
for i in range(length-3):
    for j in range(length-cnt+1):
        if int(str_list[j:j+cnt])%2019 == 0:
            result += 1
    cnt += 1
 
print(result)

### FIXED CODE ###

S = str(input())
N = len(S)

num = [0] * 2019
num[0] = 1
prev = 0
result = 0
_10 = 1
for i in range(N-1, -1, -1):
    prev = (prev + int(S[i]) * _10) % 2019
    _10 *= 10
    _10 %= 2019
    result += num[prev]
    num[prev] += 1

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

import collections
import itertools
n = int(input())
a = list(map(int,input().split()))
for i in range(len(a)):
  o = 0
  b = a[:]
  del b[i]
  c = collections.Counter(b)
  for i in c.values():
    o += len(list(itertools.permutations([ii for ii in range(i)], 2)))/2
  print(int(o))
  

### FIXED CODE ###

from collections import Counter
def comb(x):
    return x*(x-1)//2
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
b = 0
for i in c.values():
    b+=comb(i)
for k in range(n):
    print(b-c[a[k]]+1)
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline
  from fractions import gcd
  def lcm(a, b):
      return a * b // gcd(a, b)
  
  N = int(input())
  A = list(map(int,input().split()))
  MOD = 10**9+7
  
  L = 1
  for a in A:
    L = lcm(a,L)
  ans = 0
  for a in A:
    ans += L//a
    ans %= MOD
  print(ans)

if __name__ == '__main__':
  main()

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  from fractions import gcd
  def lcm(a, b):
      return a * b // gcd(a, b)
  
  N = int(input())
  A = tuple(sorted(list(map(int,input().split()))))
  MOD = 10**9+7
  
  L = 1
  for a in A:
    L = lcm(a,L)
  ans = 0
  for a in A:
    #ans += L//a
    ans += L*pow(a,MOD-2,MOD)
  print(ans%MOD)

if __name__ == '__main__':
  main()