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

import collections
import bisect
n=int(input())
a=collections.Counter(map(int,input().split()))
a=list(a.values())
a.sort()
b=[0]*len(a)
b[0]=a[0]
for i in range(len(a)-1):
    b[i+1]=b[i]+a[i+1]
s=sum(a)
ans=[i for i in range(0,n+1)]
ans=ans[::-1]
for t in range(1,n+1):
    for A in ans:
        z=bisect.bisect_right(a,A)
        if A*t<=(b[z-1] if z>=1 else 0)+A*(len(b)-z):
            print(A)
            break

### FIXED CODE ###

import collections
import bisect
n=int(input())
a=collections.Counter(map(int,input().split()))
a=list(a.values())
a.sort()
b=[0]*len(a)
b[0]=a[0]
for i in range(len(a)-1):
    b[i+1]=b[i]+a[i+1]
s=sum(a)
#print(a,b)
ans=[i for i in range(0,n+1)]
ans=ans[::-1]
for t in range(1,n+1):
    ANS=ans[n+(-n//t):]
    #print(ANS)
    for A in ANS:
        z=bisect.bisect_right(a,A)
        #print(z)
        if A*t<=(b[z-1] if z>=1 else 0)+A*(len(b)-z):
            print(A)
            break
### BUGGY CODE ###

# vim: fileencoding=utf-8


def main():
    N = int(input())
    for n in range(1, N + 1):
        ans = 0
        if n <= 5:
            print(ans)
            continue
        for x in range(1, int((N + 1) / 6) + 1):
            tx = x ** 2
            if tx >= n:
                break
            for y in range(1, int((N + 1) / 6) + 1):
                ty = tx + y ** 2 + x * y
                if ty >= n:
                    break
                for z in range(1, int((N + 1) / 6) + 1):
                    t = ty + z ** 2 + y * z + z * x
                    if t == n:
                        ans += 1
        print(ans)


if __name__ == "__main__": main()


### FIXED CODE ###

# vim: fileencoding=utf-8


def main():
    N = int(input())
    ans = [0] * N
    for x in range(1, 101):
        for y in range(1, 101):
            for z in range(1, 101):
                t = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x - 1
                if t >= len(ans):
                    break
                ans[t] += 1

    print(*ans)


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

# 頂点を3回ずつに持つ (x歩目の着地）
# 最短路

import sys
import numpy as np
from scipy.sparse import *
input = sys.stdin.readline
N,M = map(int,input().split())
if M == 0:
  print(-1)
  exit()
UV = np.array([input().split() for _ in range(M)], dtype=np.int32)
U = UV[:,0]
V = UV[:,1]
S,T = map(int,input().split())
rows = np.concatenate([3*U, 3*U+1, 3*U+2])
cols = np.concatenate([3*V+1, 3*V+2, 3*V])

graph = csr_matrix((np.ones_like(rows), (rows, cols)), (3*N+3, 3*N+3))
dist = csgraph.dijkstra(graph, indices = 3*S)

answer = -1 if dist[3*T] > 3*N else int(dist[3*T]//3)
print(answer)


### FIXED CODE ###

# 頂点を3回ずつに持つ (x歩目の着地）
# 最短路

import sys
input = sys.stdin.readline
N,M = map(int,input().split())
if M == 0:
  print(-1)
  exit()
edge = [[] for _ in range(N+1)]
for _ in range(M):
  u,v = map(int,input().split())
  edge[u].append(v)
S,T = map(int,input().split())

INF = 10 ** 9
dist = [[INF,INF,INF] for _ in range(N+1)]

d = 0
q = [S]
while q:
  d += 1
  r = d % 3
  qq = []
  for u in q:
    for v in edge[u]:
      if dist[v][r] == INF:
        dist[v][r] = d
        qq.append(v)
  q = qq

d = dist[T][0]
answer = -1 if d == INF else d // 3
print(answer)
### BUGGY CODE ###

from bisect import bisect_left,bisect
N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
for b,c in BC:
  A.sort()
  i = bisect_left(A,c)
  if c <= A[0]:
    continue
  if b < i:
    A[:b] = [c]*b
  else:
    A[:i] = [c]*i
print(sum(A))

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [(A[i], 1) for i in range(N)]
for _ in range(M):
    B, C = map(int, input().split())
    BC.append((C,B))
BC = sorted(BC,reverse = True)
ans = 0
a = 0
count = N
for c,b in BC:
  lamb = min(count,b)
  ans += c * lamb
  count -= lamb

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

from collections import deque

s=list(input())
Q=int(input())

d=deque(s)

for i in range(Q):
    tmp=list(input())
    if tmp[0] == "1":
        d.reverse()
    else:
        if tmp[2] == "1":
            d.appendleft(tmp[4])
        else:
            d.append(tmp[4])
ans=list(d)
answer="".join(ans)
print(answer)

### FIXED CODE ###

from collections import deque
import sys
input2 = sys.stdin.readline()

s=list(input2)
Q=int(input())
direction=0
d=deque(s)
d.pop()

for i in range(Q):
    tmp=list(input())
    if tmp[0] == "1":
        if direction == 0:
            direction = 1
        else:
            direction = 0
    else:
        if tmp[2] == "1":
            if direction == 0:
                d.appendleft(tmp[4])
            else:
                d.append(tmp[4])
        else:
            if direction == 0:
                d.append(tmp[4])
            else:
                d.appendleft(tmp[4])
if direction==1:
    d.reverse()
ans=list(d)
answer="".join(ans)
print(answer)
### BUGGY CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7


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

    l = A[0]
    for i in range(1, N):
        l = l * A[i] // gcd(l, A[i])

    ans = 0
    for a in A:
        ans += l // a
    print(ans % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7


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

    l = A[0]
    for i in range(1, N):
        l = l * A[i] // gcd(l, A[i])

    print(sum([l // a for a in A]) % MOD)


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

def f(n):
  cnt = 0
  for i in range(int((n-3)**1/2 //1)):
    for j in range(int((n-3)**1/2 //1)):
      for k in range(int((n-3)**1/2 //1)):
        if (i+1)**2 + (j+1)**2 + (k+1)**2 + (i+1)*(j+1) + (j+1)*(k+1) + (k+1)*(i+1) == n:
          cnt += 1
  return cnt
    
N = int(input())
for i in range(N):
  print(f(i+1))

### FIXED CODE ###

n = int(input())
a = [0]*n
cnt = 0
for i in range(1,100):
  for j in range(1,100):
    for k in range(1,100):
      b = i**2 + j**2 + k**2 + i*j + j*k + k*i
      if b <= n:
        a[b-1] += 1

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

import math
from functools import reduce


#A,B,C=(int(x) for x in input().split())
N=int(input())
#A=list(map(int, input().split()))

l=[(a,b,c) for a in range (1,N+1) for b in range  (1, N+1) for c in range (1, N+1)]



def gcd_list(numbers):
    return reduce(math.gcd, numbers)

i=0

for k in range(N**3):
    m=gcd_list(l[k])
    i=i+m
    
print(i)

### FIXED CODE ###

import math

K=int(input())

total=0

for i in range(1,K+1):
  for j in range(1,K+1):
    g=math.gcd(i,j)
    for k in range(1,K+1):
      a=math.gcd(g,k)
      total+=a

print(total)
### BUGGY CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit


@njit
def make_my_route(route,A,N):
    pre = 1
    for i in range(N):
        now = A[pre-1]
        route = np.append(route,now)
        temp = np.sum(route == now)
        if temp == 2:
            break
        pre = now
    return route


def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A = np.array(A)

    route = np.array([1])

    route = make_my_route(route,A,N)
    now = route[-1]
    start = int(np.where(route == now)[0][0])

    if K < start:
        res = route[K]
    elif start+1 != N:
        K -= start
        loop = route[start:-1]
        # print(loop,K)
        M = len(loop)
        K %= M
        res = loop[K]
    else:
        res = route[K]

    print(res)



main()


### FIXED CODE ###

# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
# from numba import njit


def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))

    s = []
    ord = [-1] * (N+1)
    v = 1

    while ord[v] == -1:
        ord[v] = len(s)
        s.append(v)
        v = A[v-1]

    c = len(s) - ord[v]
    l = ord[v]

    if K < l:
        res = s[K]
    else:
        K -= l
        K %= c
        res = s[l+K]

    print(res)



main()
### BUGGY CODE ###

H,W,M = map(int, input().split())
width = [0]*W
height = [0]*H

st = set()
for i in range(M):
  y, x = map(int, input().split())
  st.add((x - 1,y - 1))
  width[x-1] += 1
  height[y-1] += 1

indexW = [i for i, v in enumerate(width) if v == max(width)]
indexH = [i for i, v in enumerate(height) if v == max(height)]

maxW = max(width)
maxH = max(height)

ans = maxW + maxH 

#それぞれ列と行の最大値の中から適当に１つずつ列と行を選ぶ
tmpX = indexW[0]
tmpY = indexH[0]

#HeightとWidthのそれぞれの最大値の点(x, y)に爆弾がない場合があるかどうか
flag = 0

#print(f"maxW : {maxW}")
#print(f"maxH : {maxH}")
#print(f"set : {st}")
#print(f"indexH {indexH}")
#print(f"indexW {indexW}")

#Heightの最大値と、widthのそれぞれを全探索
for x in indexW:
  y = tmpY
  if not (x, y) in st:
    flag = 1
    break


for y in indexH:
  x = tmpX
  if not (x, y) in st:
    flag = 1
    break

if flag == 1:
  print(ans)
else:
  print(ans - 1);


### FIXED CODE ###

H,W,M = map(int, input().split())
width = [0]*W
height = [0]*H

st = set()
for i in range(M):
  y, x = map(int, input().split())
  st.add((x - 1,y - 1))
  width[x-1] += 1
  height[y-1] += 1

maxW = max(width)
maxH = max(height)

indexW = [i for i, v in enumerate(width) if v == maxW]
indexH = [i for i, v in enumerate(height) if v == maxH]

ans = maxW + maxH 

#それぞれ列と行の最大値の中から適当に１つずつ列と行を選ぶ
tmpX = indexW[0]
tmpY = indexH[0]

#HeightとWidthのそれぞれの最大値の点(x, y)に爆弾がない場合があるかどうか
flag = 0

#print(f"indexH {indexH}")
#print(f"indexW {indexW}")

#Heightの最大値と、widthのそれぞれを全探索
for x in indexW:
  y = tmpY
  if not (x, y) in st:
    flag = 1
    break


for y in indexH:
  x = tmpX
  if not (x, y) in st:
    flag = 1
    break

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

R,G,B,N=map(int, input().split())
count=0
for p1 in range(0,N+1,R):
    for p2 in range(0,N-p1+1,G):
        rR = p1
        gG = p2
        bB = N-p1-p2
        if rR%R==0 and gG%G==0 and bB%B==0:
            count+=1
print(count)

### FIXED CODE ###

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

count=0
for p1 in range(0,N+1,R):
    for p2 in range(0,N-p1+1,G):
        rR = p1
        gG = p2
        bB = N-p1-p2
        if bB%B==0:
            count+=1
print(count)
### BUGGY CODE ###

from fractions import gcd


k = int(input())
ans = 0

for a in range(1, k + 1):
  for b in range(1, k+1):
    g = gcd(a,b)
    for c in range(1, k+1):
      ans += gcd(g,c)

print(ans)

### FIXED CODE ###

from math import gcd

k=int(input())
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for g in range(1,k+1):
      ans += gcd(gcd(i,j), g)

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

n,k = map(int, input().split())
cnt=0
while n!=1:
    n=n//k
    cnt+=1
print(cnt+1)
    




### FIXED CODE ###

n,k = map(int, input().split())
cnt=0
while n!=0:
    n=n//k
    cnt+=1
print(cnt)
### BUGGY CODE ###

N,Q = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N - 1)]
px = [list(map(int,input().split())) for _ in range(Q)]
ab.sort()
px.sort()


# connection = [[] for _ in range(N - 1)]
# ans = [[] for _ in range(N)]
plus = [0 for _ in range(N)]

for p,x in px:
        plus[p - 1] = x + plus[p - 1]

for a,b in ab:
        plus[b - 1] = plus[b - 1] + plus[a - 1]
for p in plus:
        print(p)

### FIXED CODE ###

def main():
        N,Q = map(int,input().split())
        ab = [list(map(int,input().split())) for _ in range(N - 1)]
        px = [list(map(int,input().split())) for _ in range(Q)]
        ab.sort()
        # px.sort()
        plus = [0 for _ in range(N)]

        for p,x in px:
                plus[p - 1] += x 

        for a,b in ab:
                plus[b - 1] += plus[a - 1]
        for p in plus:
                print(p)

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

N,Q = input().split()
Q = int(Q)
S = input()

list1 = []

for i in range(Q):
    l,r = map(int,input().split())
    l = l - 1
    list1.append(S[l:r].count('AC'))

for i in list1:
    print(i)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t=[0]*(N+1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

n,m=map(int,input().split())
a = list(int(input()) for i in range(m))
INF=1000000007
dp=[0]*(n+1)
dp[0]=1
if 1 in a:
    dp[1]=0
else:
    dp[1]=1
for i in range(2,n+1):
    if i in a:
        continue
    dp[i]=dp[i-1]+dp[i-2]
    dp[i]%=INF
print(dp[n])

### FIXED CODE ###

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

INF=1000000007
dp=[0]*(n+1)
dp[0]=1
if 1 in a:
    dp[1]=0
else:
    dp[1]=1
for i in range(2,n+1):
    if i in a:
        continue
    dp[i]=dp[i-1]+dp[i-2]
    dp[i]%=INF
print(dp[n])
### BUGGY CODE ###

#from math import sqrt
#from heapq import heappush, heappop
#from collections import deque

#a, b = [int(v) for v in input().split()]

n = int(input())
n0 = n


count = 0
while n > 0:
    #print(n, count)
    v = n % 10
    n //= 10
    if v < 5:
        count += v
    elif v == 5:
        if (n % 10) >= 5:
            n += 1
        count += 5
    else:
        count += 10 - v
        n += 1
print(count)


### FIXED CODE ###

#from math import sqrt
#from heapq import heappush, heappop
#from collections import deque

#a, b = [int(v) for v in input().split()]

n = input()

flag = 0
count = 0
for i in range(len(n) - 1, -1, -1):
    c = n[i]
    v = int(c) + flag

    if v == 10:
        v = 0
        flag = 1
    else:
        flag = 0
    if v < 5:
        count += v
    elif v == 5:
        if i != 0 and int(n[i-1]) >= 5:
            flag = 1
        count += 5
    else:
        count += 10 - v
        flag = 1
print(count + flag)
### BUGGY CODE ###

n,k = map(int, input().split())
p = list(map(lambda x: (int(x)+1)/2, input().split()))

ans = 0
for i in range(n-k+1):
  t = sum(p[i:i+k])
  if ans < t: ans = t
print(ans)

### FIXED CODE ###

n,k = map(int, input().split())
p = list(map(int, input().split()))

# 値ごとの期待値を取得
s = [0]*n
for i in range(n):
  s[i] = (p[i]+1)/2

# 期待値を累積していく
p = [0]*(n+1)
for i in range(1, n+1):
  p[i] = p[i-1] + s[i-1]

# 下記の方法で隣接する期待値合計を取得し、比較を行う。
# 隣接する期待値の合計　= 対象とする範囲の最大累積和　- 対象外範囲の最大累積和
ans = 0
for i in range(n-k+1):
  ans = max(ans, p[i+k] - p[i])

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

s = input()
t = input()

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

for i in range(1,len(s)+1):
    for j in range(1, len(t)+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

# DPを逆に辿って復元する
ans = ""
i = len(s)
j = len(t)
while( i>0 and j>0):
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1

print(ans)


### FIXED CODE ###

s = input()
t = input()

dp = [[0]*(len(t)+1) for i in range(len(s)+1)]

for i in range(len(s)):
  for j in range(len(t)):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j]+1
    else:    
      dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
           
ans = ""
i = len(s)
j = len(t)
while i > 0 and j > 0 :
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] +ans
        i -= 1
        j -= 1
print(ans)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

L = []

for i in range(len(A)):
    for j in range(len(B)):
        for k in range(len(C)):
            tmp = A[i] + B[j] + C[k]
            L.append(tmp)

L.sort(reverse=True)

for i in range(K):
    print(L[i])

### FIXED CODE ###

#%%
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()

bc = [0] * (y * z)
q = 0
for i in range(y):
    for j in range(z):
        bc[q] = b[i] + c[j]
        q += 1

bc.sort(reverse=True)
r = len(bc)
bc = bc[:min(k, r)]

abc = [0] * (x * min(k, r))
q = 0
for i in range(min(k, r)):
    for j in range(x):
        abc[q] = bc[i] + a[j]
        q += 1

abc.sort(reverse=True)
for i in range(min(k, x*y*z)):
    print(abc[i])
### BUGGY CODE ###

n,m=map(int,input().split())
lists=list(map(int,input().split()))
uselist=[]
for some in lists:
    some=some//2
    uselist.append(some)

import fractions
import math
ans = uselist[0]
for i in range(1, n):
    ans = ans* uselist[i] // fractions.gcd(ans, uselist[i])

flags=True
for some in uselist:
    a=ans//some
    if a%2==0:
        flags=False
        break
if flags:
    p=math.floor(m/ans)
    if p%2==0:
      print(p//2)
    elif p%2!=0:
      print(p//2+1)
    
else:
    print(0)

### FIXED CODE ###

n,m=map(int,input().split())
lists=list(map(int,input().split()))
uselist=[]
for some in lists:
    some=some//2
    uselist.append(some)

import fractions
import math
ans = uselist[0]
for i in range(1, n):
    ans = ans* uselist[i] // fractions.gcd(ans, uselist[i])

flags=True
for some in uselist:
    a=ans//some
    if a%2==0:
        flags=False
        break
if flags:
    p=math.floor(m/ans)
    if p%2==0:
      print(p//2)
    elif p%2!=0:
      print(p//2+1)
    
else:
    print(0)
### BUGGY CODE ###

N=int(input())

S=[]

for i in range(N):
    a=input()
    if S.count(a) == 0:
        S.append(a)

print(len(S))



### FIXED CODE ###

N=int(input())

S={}

for i in range(N):
    a=input()
    if a in S:
        pass
    else:
        S[a] = 0

print(len(S))
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

AB = []
for i, a in enumerate(A):
    for j, b in enumerate(B):
        AB.append(a + b)

AB.sort(reverse=True)

ABC = []
for i, ab in enumerate(AB[:K+1]):
    for j, c in enumerate(C):
        ABC.append(ab + c)

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))


A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

ABC = []

for i, a in enumerate(A):
    for j, b in enumerate(B):
        if (i + 1) * (j + 1) > K:
            break
        for k, c in enumerate(C):
            if (i + 1) * (j + 1) * (k + 1) > K:
                break
            ABC.append(a + b + c)

ABC.sort(reverse=True)
for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
C = [list(input()) for i in range(H)]
X = [1,0,-1,0]
Y = [0,-1,0,1]
INF = 10**9

Q = deque()
dist = [[INF]*W for i in range(H)]

for x in range(W):
  for y in range(H):
    if C[y][x] == "#":
      Q.append((y,x))
      dist[y][x] = 0
      while Q:
        y,x = Q.popleft()
        for i in range(4):
          nx = x + X[i]
          ny = y + Y[i]
          if (0 <= nx < W) and (0 <= ny < H) and dist[y][x]+1 <= dist[ny][nx] and (C[ny][nx] != "#"):
            dist[ny][nx] = dist[y][x] + 1
            Q.append((ny,nx))
ans = 0
for i in range(H):
  ans = max(ans,max(dist[i]))
print(ans)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
A = [input() for i in range(H)]
X = [1,0,-1,0]
Y = [0,-1,0,1]

INF = 99999
dp = [[-1]*W for i in range(H)]
q = deque()
for y, row in enumerate(A):
  for x,c in enumerate(row):
    if c == "#":
      dp[y][x] = 0
      q.append((y,x))
while q:
  y,x = q.popleft()
  d = dp[y][x]
  for i in range(4):
    nx = x + X[i]
    ny = y + Y[i]
    if (0 <= nx < W) and (0 <= ny < H) and (dp[ny][nx] == -1):
      dp[ny][nx] = d + 1
      q.append((ny,nx))
print(max(max(row) for row in dp))
### BUGGY CODE ###

from collections import Counter

mod = 10 ** 9 + 7

N, *A = map(int, open(0).read().split())

C = Counter()
for a in A:
    if a in C:
        continue
    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            C[i] = max(C[i], cnt)
        i += 1
    if a > 1:
        C[a] = max(C[a], 1)

L = 1
for i, c in C.items():
    L *= pow(i, c, mod)
    L %= mod

ans = 0
for a in A:
    ans += L * pow(a, mod - 2, mod)
    ans %= mod

print(ans)

### FIXED CODE ###

from fractions import gcd
from functools import reduce

def main():
    lcm = lambda a, b: a * b // gcd(a, b)
    mod = 10 ** 9 + 7

    N, *A = map(int, open(0).read().split())

    L = reduce(lcm, A)
    print(sum(L // a for a in A) % mod)

main()
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
AC = [S[i:i+2] == 'AC'for i in range(len(S)-1)]
AC = [sum(AC[:i+1]) for i in range(len(AC))]
AC.insert(0, 0)
for i in range(Q):
    l, r = map(int, input().split())
    # print(AC[r-1], AC[l-1])
    print(AC[r-1]-AC[l-1])


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
AC = [int(S[i:i+2] == 'AC') for i in range(len(S)-1)]
for i in range(1, len(AC)):
    AC[i] = AC[i] + AC[i-1]
AC.insert(0, 0)
for i in range(Q):
    l, r = map(int, input().split())
    # print(AC[r-1], AC[l-1])
    print(AC[r-1]-AC[l-1])
### BUGGY CODE ###

N = int(input())
S = input()
result = 0
'''
for i in range(N):
    print(result)
    for j in range(i+1,N):
        if S[i] != S[j]:
            for k in range(j ,N):
                if k- j == j - i:
                    continue
                if S[j] != S[k] and S[i] != S[k]:
                    result +=1
print(result)
'''
for i in range(N):
    #print(result)
    for j in range(i + 1, N):
        if S[i] != S[j]:
            target = 'RGB'.strip(S[i]) if S[i] != 'G' else 'RB'
            target = target.strip(S[j])
            result += S.count(target, j + 1, N)
            if 2*j-i < N and S[2 * j - i] == target:
                result -= 1
print(result)


### FIXED CODE ###

N = int(input())
S = input()
result = 0
'''
for i in range(N):
    print(result)
    for j in range(i+1,N):
        if S[i] != S[j]:
            for k in range(j ,N):
                if k- j == j - i:
                    continue
                if S[j] != S[k] and S[i] != S[k]:
                    result +=1
print(result)
'''
r = S.count('R')
g = S.count('G')
b = S.count('B')
target = set('RGB')
result = r * g * b
for i in range(N):
    for j in range(1, min(i, (N - i - 1)) + 1):
        if target == set(S[i] + S[i-j] + S[j + i]):
            result -= 1
print(result)
### BUGGY CODE ###

def edu_dp_d_knapsack1():
    n, c = map(int, input().split())
    w, v = [], []
    for _ in range(n):
        a, b = map(int, input().split())
        w.append(a)
        v.append(b)
    dp = [[0] * (c+1) for _ in range(n)]
    dp[0][w[0]] = v[0]
    for i in range(1, n):
        for j in range(0, c+1):
            dp[i][j] = dp[i-1][j]
            if j >= w[i]:
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]]+v[i])
    print(max(dp[n-1]))

edu_dp_d_knapsack1()

### FIXED CODE ###

def edu_dp_d_knapsack1():
    n, c = map(int, input().split())
    w, v = [], []
    for _ in range(n):
        a, b = map(int, input().split())
        w.append(a)
        v.append(b)
    dp = [[0] * (c + 1) for _ in range(n)]
    dp[0][w[0]] = v[0]
    for i in range(1, n):
        for j in range(0, c + 1):
            dp[i][j] = dp[i - 1][j]
            if j >= w[i]:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i])
    print(max(dp[n - 1]))
edu_dp_d_knapsack1()
### BUGGY CODE ###

from sys import stdin

s=stdin.readline().rstrip().split()
N=int(s[0])
M=int(s[1])
count=0
total=0

a=stdin.readline().rstrip().split()
for i in range(N):
  a[i]=int(a[i])

for i in range(M):
  a[a.index(max(a))]=a[a.index(max(a))]//2

for i in range(N):
  total=total+a[i]
  
print(total)

### FIXED CODE ###

from sys import stdin
import heapq

s=stdin.readline().rstrip().split()
N=int(s[0])
M=int(s[1])

a=stdin.readline().rstrip().split()
for i in range(N):
  a[i]=int(a[i])*(-1)
  
heapq.heapify(a)
for i in range(M):
  t=-(-heapq.heappop(a)//2)
  heapq.heappush(a,t)
print(sum(a)*(-1))