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

# test
class BIT:
  ini = 0
  def __init__(s, num):
    s.N = 1
    while s.N <= num:
      s.N *= 2
    s.T = [s.ini] * s.N
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, n): # xにnを加える
    k = x + 1
    s.T[k - 1] += n
    k += k & -k
    while k <= s.N:
      s.T[k - 1] += n
      k += k & -k
  def getV(s, x): # xまでの和(x含む)
    if x < 0: return 0
    x += 1
    ans = s.T[x - 1]
    x -= x & -x
    while x != 0:
      ans += s.T[x - 1]
      x -= x & -x
    return ans

N, Q = list(map(int, input().split()))
a = list(map(int, input().split()))
Query = [list(map(int, input().split())) for _ in range(Q)]
  
bit = BIT(N)
bit.set(a)

for q in Query:
  if q[0] == 0:
    _, p, x = q
    bit.update(p, x)
  else:
    _, l, r = q
    print(bit.getV(r - 1) - bit.getV(l - 1))

### FIXED CODE ###

# test
class BIT:
  ini = 0
  def __init__(s, num):
    s.N = 1
    while s.N <= num:
      s.N *= 2
    s.T = [s.ini] * s.N
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, n): # xにnを加える
    k = x + 1
    s.T[k - 1] += n
    k += k & -k
    while k <= s.N:
      s.T[k - 1] += n
      k += k & -k
  def getV(s, x): # xまでの和(x含む)
    if x < 0: return 0
    x += 1
    ans = s.T[x - 1]
    x -= x & -x
    while x != 0:
      ans += s.T[x - 1]
      x -= x & -x
    return ans

N, Q = list(map(int, input().split()))
a = list(map(int, input().split()))
Query = [list(map(int, input().split())) for _ in range(Q)]
  
bit = BIT(N)
bit.set(a)

for q in Query:
  if q[0] == 0:
    _, p, x = q
    bit.update(p, x)
  else:
    _, l, r = q
    print(bit.getV(r - 1) - bit.getV(l - 1))
### BUGGY CODE ###

n= int(input())
a=[]
k=0
for _ in range(n):
  a.append(int(input()))
for i in range(n):
  k=0
  k+=a[i]
  a.pop(i)
  print(max(a))
  a.insert(i,k)

### FIXED CODE ###

n=int(input())
d=[]
for i in range(n):
  d.append(int(input()))
x=sorted(d)
for j in range(n):
  if d[j]==x[-1]:
    print(x[-2])
  else:
    print(x[-1])
### BUGGY CODE ###

H,N = map(int,input().split())
magicL =[]
for x in range(N):
    magic = list(int(i) for i in input().split())
    magicL.append(magic)

ml = magicL
dp = [10**9 for i in range(H +1)]
dp [0] = 0
for i in range(N):
    for w in range(H +1):
        dp[min(w+ml[i][0],H)] = min(dp[min(w+ml[i][0],H)],dp[w]+ml[i][1])
print(dp[H])

### FIXED CODE ###

H,N = map(int,input().split())
magicL =[]
for x in range(N):
    magic = list(int(i) for i in input().split())
    magicL.append(magic)
 
ml = magicL
dp = [10**9 for i in range(H +1)]
dp [0] = 0
for i in range(N):
    for w in range(H +1):
        dp[min(w+ml[i][0],H)] = min(dp[min(w+ml[i][0],H)],dp[w]+ml[i][1])
print(dp[H])
### BUGGY CODE ###

import collections

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

# N = 5
# A = [1, 1, 2, 1, 2]

c = collections.Counter(A)
d = {}
for i in c:
    # val = uni_vals[0]
    ans = 0
    for j in c:
        n = c[j]
        if j == i:
            n -= 1
        ans += (n*(n-1))/2
    d[i] = ans

for i in range(N):
    print(int(d[A[i]]))


### FIXED CODE ###

from collections import defaultdict, Counter

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

d = defaultdict(int)
for a in A:
    d[a] += 1

all = 0
for val in d.values():
    all += val * (val - 1) / 2

all = int(all)
val_cnt = Counter(A)
for a in A:
    print(all - (val_cnt[a] - 1))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

q = int(input())
v_to_qi = [[] for _ in range(n)]
v_to_l = [[] for _ in range(n)]
flag = [False] * n
for i in range(q):
    v, l = map(int, input().split())
    v -= 1
    v_to_qi[v].append(i)
    v_to_l[v].append(l)
    flag[v] = True
    while v > 0:
        v = (v - 1) // 2
        flag[v] = True

MAX = 10**5
# dp[i+1][j] = (i番目まで見て重さの合計がj以下のの時の価値の最大値)
dp = [[0] * (MAX + 1) for _ in range(20)]
ans = [0] * q


def dfs(v, depth):
    for j in range(MAX + 1):
        if j < items[v][1]:
            dp[depth + 1][j] = dp[depth][j]
        else:
            dp[depth + 1][j] = max(dp[depth][j],
                                   dp[depth][j - items[v][1]] + items[v][0])

    if len(v_to_qi[v]) > 0:
        for i in range(len(v_to_qi[v])):
            ans[v_to_qi[v][i]] = dp[depth + 1][v_to_l[v][i]]

    if v * 2 + 1 < n and flag[v * 2 + 1]:
        dfs(v * 2 + 1, depth + 1)
    if v * 2 + 2 < n and flag[v * 2 + 2]:
        dfs(v * 2 + 2, depth + 1)


dfs(0, 0)
print(*ans, sep='\n')


### FIXED CODE ###

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

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


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

N = int(input())
tmp = input().split(" ")
l = [int(i) for i in tmp]
ans = 1
ll = [min(l[:i+1]) for i in range(N)]
for i in range(1,N):
  if ll[i-1] > l[i]:
    ans+=1
print(ans)


### FIXED CODE ###

N = int(input())
tmp = input().split(" ")
l = [int(i) for i in tmp]
ans = 1
ll = list()
ll.append(l[0])
for i in range(1,N):
    ll.append(min(ll[i-1],l[i]))
for i in range(1,N):
  if ll[i-1] > l[i]:
    ans+=1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
lst = []
num = [1]*n
ans = 0
lst_append = lst.append
s_all = [sorted(input()) for _ in range(n)]
for s in s_all:
    if s not in lst:
        lst_append(s)
    else:
        pos = lst.index(s)
        ans += num[pos]
        num[pos] += 1

print(int(ans))

### FIXED CODE ###

from collections import defaultdict
N = int(input())
dict = defaultdict(int)
ans = 0
for i in range(N):
    s = ''.join(sorted(input()))
    ans += dict[s]
    dict[s] += 1
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
from numba import njit
input = sys.stdin.buffer.readline

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

n = min(2**10, N)

dp = np.zeros((n, 10**5+1), np.int32)
dp[0, vws[0][1]:] = vws[0][0]
for i in range(1, n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])

@njit(cache = True)
def func(vws_choose, L):
    bits = np.arange(1 << len(vws_choose))
    values = np.zeros_like(bits, np.int32)
    weights = np.zeros_like(bits, np.int32)
    for i in range(len(vws_choose)):
        indices = np.nonzero(np.bitwise_and(bits, 1<<i))
        values[indices] += vws_choose[i][0]
        weights[indices] += vws_choose[i][1]

    mask = (weights <= L)     
    print(np.amax(dp[V][L - weights[mask]] + values[mask]))


Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V][L])
    else:
        vws_choose = []
        while V >= n:
            vws_choose.append(vws[V])
            V = (V-1) // 2

        func(np.array(vws_choose), L)


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

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

n = min(2**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    ret = 0
    for v, w in zip(values, weights):
        if w <= L:
            ret = max(dp_[L - w] + v, ret)
    return ret

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))
### BUGGY CODE ###

#
import sys
import math

# ひとつ入力
n = int(input())

# initial state
a = [int(i) for i in input().split()] 
# last state
b = [int(i) for i in input().split()] 

answer = 0
answer_p = -1
while answer >= 0:
    answer_p = answer
    max_diff=0
    max_diff_i=-1
    for i in range(n):
        diff = b[i] - a[i]
        if max_diff < diff:
            max_diff = diff
            max_diff_i = i
        if b[i] < 1:
            print(-1)
            exit()
    if max_diff < 0:
        print(-1)
        exit()
    elif max_diff==0:
        for i in range(n):
            if b[i] != a[i]:
                print(-1)
                exit()
        print(answer)
        exit()
    else:
        if max_diff_i==n-1:
            answer += ( (b[n-1]-a[n-1]) // (b[0]+b[n-2]) )
            b[n-1] = (b[n-1]-a[n-1]) % (b[0]+b[n-2]) +a[n-1]
#            b[n-1] = b[n-1] - b[0] - b[n-2]
        else:
            answer += ( (b[max_diff_i]-a[max_diff_i]) // (b[max_diff_i+1]+b[max_diff_i-1]) )
            b[max_diff_i] = (b[max_diff_i]-a[max_diff_i]) % (b[max_diff_i+1]+b[max_diff_i-1]) + a[max_diff_i]
#            b[max_diff_i] = b[max_diff_i] - b[max_diff_i+1] - b[max_diff_i-1]
    if answer == answer_p:
        print(-1)
        exit()
#    print(a,b,max_diff,max_diff_i)




### FIXED CODE ###

#
import sys
import math

# ひとつ入力
n = int(input())

# initial state
a = [int(i) for i in input().split()] 
# last state
b = [int(i) for i in input().split()] 

answer = 0
answer_p = -1
while answer >= 0:
    answer_p = answer
    for i in range(n):
        tmp = b[(i-1)%n] + b[(i+1)%n]
        if 0 < tmp < b[i] and a[i] < b[i]:
            res = (b[i]-a[i]) // (b[(i+1)%n]+b[(i-1)%n])
            answer += res
            b[i] -= res * (b[(i+1)%n]+b[(i-1)%n])
        
    if answer == answer_p:
        break
#    print(a,b,answer)

for i in range(n):
    if a[i] != b[i]:
        print(-1)
        exit()
print(answer)
### BUGGY CODE ###

n, m = map(int, input().split())
x = [[int(i), 0] for i in input().split()]
x.sort(key=lambda a: a[0])
for i in range(m - 1):
    x[i][1] = x[i + 1][0] - x[i][0]

if n >= m:
    print(0)
else:
    sumdis = sum(map(lambda a: a[1], x))
    h = 0
    skipdis = 0
    while h < n - 1:
        maxdis = max(x, key=lambda a: a[1])
        skipdis += maxdis[1]
        x.remove(maxdis)
        h += 1
    print(sumdis - skipdis)

### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    t = list(map(int, input().split()))
    if n >= m:
        return 0
    t.sort()
    x = [[t[i], t[i+1] - t[i]] for i in range(m-1)]
    x.append([t[m-1], 0])
    x.sort(key=lambda a: a[1], reverse=True)
    sum_dis = t[m-1] - t[0]
    skip_dis = sum([x[i][1] for i in range(n - 1)])
    return sum_dis - skip_dis


print(main())
### BUGGY CODE ###

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

ans = 0
for i in range(n):
  m = []
  for j in range(i+1):
    m.append(p[j])
  if min(m) == m[-1]:
    ans += 1
print(ans)

### FIXED CODE ###

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

ans = 0
for i in p:
  if i <= p[0]:
    p[0] = i
    ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
S = list(input())

ans = 0

for i in range(10):
  for j in range(10):
    for k in range(10):
      Flag1 = True
      Flag2 = False
      Flag3 = False
      for x in S:
        if Flag3:
          if x == str(k):
            ans += 1
            break
        if Flag2:
          if x == str(j):
            Flag2 = False
            Flag3 = True
        if Flag1:
          if x == str(i):
            Flag1 = False
            Flag2 = True

print(ans)

### FIXED CODE ###

N = int(input())
S = [int(i) for i in input()]

ans = 0

for i in range(10):
  for j in range(10):
    for k in range(10):
      Flag1 = True
      Flag2 = False
      Flag3 = False
      for x in S:
        if Flag3:
          if x == k:
            ans += 1
            break
        if Flag2:
          if x == j:
            Flag2 = False
            Flag3 = True
        if Flag1:
          if x == i:
            Flag1 = False
            Flag2 = True

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

import sys

input = sys.stdin.readline

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()))

d = []
for aa in a:
    for bb in b:
        d.append(aa + bb)

d = list(sorted(d, reverse=True)[:K])

e = []
for cc in c:
    for dd in d:
        e.append(cc + dd)

for ee in sorted(e, reverse=True)[:K]:
    print(ee)


### FIXED CODE ###

# https://www.kumilog.net/entry/python-speed-comp#input-%E3%81%A8-sysstdinreadline
# https://teratail.com/questions/88396

from heapq import heapify, heappush, heappop
import sys

input = sys.stdin.readline


class Data:
    def __init__(self, value, indices):
        self.value = value
        self.indices = indices

    def __lt__(self, other):
        return self.value < other.value


X, Y, Z, K = map(int, input().split())
a = map(int, input().split())
b = map(int, input().split())
c = map(int, input().split())

a = list(sorted(a, reverse=True))
b = list(sorted(b, reverse=True))
c = list(sorted(c, reverse=True))

hq = []
heapify(hq)

t = a[0] + b[0] + c[0]
t *= -1

d = Data(t, (0, 0, 0))

heappush(hq, d)

dtpls = ((1, 0, 0), (0, 1, 0), (0, 0, 1))

st = set()

cnt = 0
for _ in range(K):
    d = heappop(hq)
    print(-d.value)
    for dtpl in dtpls:
        na = d.indices[0] + dtpl[0]
        if na >= X: continue
        nb = d.indices[1] + dtpl[1]
        if nb >= Y: continue
        nc = d.indices[2] + dtpl[2]
        if nc >= Z: continue

        nt = a[na] + b[nb] + c[nc]
        nt *= - 1

        ntpl = (na, nb, nc)
        if ntpl in st: continue
        heappush(hq, Data(nt, ntpl))
        st.add(ntpl)
### BUGGY CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections


x = int(input())
for i in range(-1000,1001):
    for j in range(-1000,1001):
        if i**5 - j**5 == x:
            print(i,j)

### FIXED CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections


x = int(input())
for i in range(-1000,1001):
    for j in range(-1000,1001):
        if i**5 - j**5 == x:
            print(i,j)
            sys.exit()
### BUGGY CODE ###

H, W = map(int, input().split())
import sys
input = sys.stdin.readline
def sc(s):
    b = None
    nc = 0
    kk = [0]*len(s)
    for i, c in enumerate(s):
        if c == ".":
            if c == b:
                nc += 1
            else:
                si = i
        else:
            if b == ".":
                for j in range(si, i):
                    kk[j] = i - si
            nc = 0
        b = c
    return kk
d = []
d2 = []
d3 = []
for h in range(H):
    s = input().strip() + "#"
    d.append(s)
    d2.append(sc(s))

for i in range(W):
    s = ""
    for j in range(H):
        s += d[j][i]
    s += "#"
    d3.append(sc(s))
r = 0
for i in range(H):
    for j in range(W):
        r = max(r, d2[i][j] + d3[j][i]-1)
print(r)


### FIXED CODE ###

H, W = map(int, input().split())
import sys
input = sys.stdin.readline
def sc(s):
    b = None
    nc = 0
    kk = [0]*len(s)
    for i, c in enumerate(s):
        if c == ".":
            if c == b:
                nc += 1
            else:
                si = i
        else:
            if b == ".":
                for j in range(si, i):
                    kk[j] = i - si
            nc = 0
        b = c
    return kk
d = []
d2 = []
d3 = []
for h in range(H):
    s = input().strip()
    d.append(s)
    d2.append(sc(s+"#"))

d = list(zip(*d))
for s in d:
    d3.append(sc("".join(s)+"#"))
r = 0
for i in range(H):
    for j in range(W):
        r = max(r, d2[i][j] + d3[j][i]-1)
print(r)
### BUGGY CODE ###

#!/usr/bin/python

import sys

p=[0]*10;mp=[];inf=65536;v=[0]*10;t=[0]*10
 
 
ans=100000
 
n,m,r=map(int,raw_input().split(' '))
 
p=map(int,raw_input().split(' '))
 
def dsss(x,now):
	global ans
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
        mp[i][j]=inf
 
for i in range(m):
	a,b,c=map(lambda x: int(x),sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)
 
for i in range(n):
	for j in range(n):
		for k in range(n):
			mp[j][k]=min(mp[j][k],mp[j][i]+mp[i][k])
 
dsss(1,0)
 
print ans


### FIXED CODE ###

#!/usr/bin/python

import sys

p=[0]*10000;mp=[];inf=65530060;v=[0]*1000;t=[0]*1000
 
 
ans=100000000

 
n,m,r=map(int,sys.stdin.readline().split(" "))



s=sys.stdin.readline().replace("\n","")

p=map(int,s.split(" "))


def dsss(x,now):
	global ans,v,p,t,mp
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
            mp[i][j]=inf


for i in range(m):
	a,b,c=map(lambda x: int(x),sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)


for i in xrange(n):
	for j in xrange(n):
		for k in xrange(n):
			if mp[j][i]+mp[i][k]<mp[j][k]:
			    mp[j][k]=mp[j][i]+mp[i][k]

dsss(1,0)
 
print ans
### BUGGY CODE ###

# unihernandez22 & Vicfred
# https://atcoder.jp/contests/abc166/tasks/abc166_d
# math, probability
from random import randint

n = int(input())

for _ in range(10**8):
    x = randint(-1000,1000)
    y = randint(-1000,1000)
    if x**5 - y**5 == n:
        print(x,y)
        break;



### FIXED CODE ###

# unihernandez22
# https://atcoder.jp/contests/abc166/tasks/abc166_d
# math
n = int(input())
for a in range(n):
    breaked = True
    for b in range(-1000, 1000):
        if a**5 - b**5 == n:
            print(a, b)
            break;
    else:
        breaked = False
    if breaked:
        break
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
M = 10**9+7
def factorize(n):
    fct = defaultdict(int)
    b, e = 2, 0
    while b*b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct[b] = e
        b, e = b+1, 0
    if n > 1:
        fct[n] = 1
    return fct
dct = defaultdict(int)
dctT = [0]*N
for i,a in enumerate(A):
    dctT[i] = factorize(a)
    for key in dct.keys() | dctT[i].keys():
        dct[key] = max(dct[key],dctT[i][key])
ans = 0
for i in range(N):
    t = 1
    for k,v in dct.items():
        t *= pow(k,v-dctT[i][k],M)
    ans += t
print(ans%M)

### FIXED CODE ###

from fractions import gcd
def lcm(a,b):
    return a*b // gcd(a,b)

N = int(input())
A = list(map(int,input().split()))
M = 10**9+7
l = 1
for a in A:
    l = lcm(l,a)
ans = 0
for a in A:
    ans += l//a
print(ans%M)
### BUGGY CODE ###

import math
def naive_cmb(n, r):
    if r < 0 or r > n:
        return 0
    return (math.factorial(n) // math.factorial(r)) // math.factorial(n-r)

S = input()

mod = [0] * (2019+1)

for i in range(1, len(S)+1):
    mod[int(S[-i:]) % 2019] += 1

ans = mod[0]

for i in range(1, 2020):
    if mod[i] >= 2:
        ans += naive_cmb(mod[i], 2)

print(ans)

### FIXED CODE ###

S = input()

n_i_to_j_mod = [0] * (2019+1) # 2019で割った余りがiになるようなSの部分連続文字列の個数
i_to_end_mod = [0] * (len(S)+1) # S[-i:](Sの後方i文字)を2019で割ったときの余り

for i in range(1, len(S)+1):
    if i == 1:
        i_to_end_mod[1] = int(S[-1]) % 2019
    else:
        i_to_end_mod[i] = (i_to_end_mod[i-1] + int(S[-i]) * pow(10, i-1, 2019)) % 2019
    n_i_to_j_mod[i_to_end_mod[i]] += 1

ans = n_i_to_j_mod[0] + (n_i_to_j_mod[0] * (n_i_to_j_mod[0]-1))//2
for i in range(1, 2019):
    if n_i_to_j_mod[i] >= 2:
        ans += (n_i_to_j_mod[i] * (n_i_to_j_mod[i]-1)) // 2
print(ans)
### BUGGY CODE ###

def count1(n):
    nx=bin(n)
    return nx.count('1')

N=int(input())
X=input()
for i in range(N):
    Ni2=X
    if X[i]=='0':
        Ni2=X[:i]+'1'+X[(i+1):] #文字列は変更できない
    else:
        Ni2=X[:i]+'0'+X[(i+1):]
    Ni=int(Ni2,2)
    ans=0
    #print(Ni)
    while Ni!=0:
        Ni=Ni%count1(Ni)
        ans+=1
    print(ans)


### FIXED CODE ###

N = int(input())
X = input()
popcount_X = X.count('1')
numX = int(X, 2)
a = numX % (popcount_X + 1)
b = numX % (popcount_X - 1) if popcount_X != 1 else 0
for i, x in enumerate(X, 1): #リストのインデクス，要素，第二引数に開始位置
    if x == '1' and popcount_X == 1:
        print(0)
        continue
    ans = 1
    if x == '1':
        temp = (b - pow(2, N - i, popcount_X - 1)) % (popcount_X - 1)
    else:
        temp = (a + pow(2, N - i, popcount_X + 1)) % (popcount_X + 1)
    while temp:
        p = format(temp, 'b').count('1') #2進数，1の個数
        temp %= p
        ans += 1
    print(ans)
### BUGGY CODE ###

from itertools import permutations
n = int(input())
v = list(map(int, input().split()))

total = 0
for permutation in list(permutations(v,n)):
    subtotal = permutation[0]
    for i in range(1, len(permutation)):
        subtotal = (subtotal + permutation[i]) / 2
    total = max(total, subtotal)
    
print(total)

### FIXED CODE ###

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

v.sort()

total = v[0]
for i in range(1, n):
    total = (total + v[i])/ 2
    
print(total)
### BUGGY CODE ###

N = int(input())
Ps = list(map(int, input().split()))
count = 0
low = -1

for i in range(N):
    low = Ps[i]

    if ( sum(x < low for x in Ps[:i]) == 0):
        count += 1

print(count)

### FIXED CODE ###

N = int(input())
Ps = list(map(int, input().split()))
count = 0
min = Ps[0]+1

for i in range(N):
    if (Ps[i] < min):
        min = Ps[i]
        count += 1

print(count)