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

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
def lcm(a, b):
    return (a * b // gcd(a, b))

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

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

### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
def lcm(a, b):
    return (a * b // gcd(a, b))

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

def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

ans = 0
for a in A:
    ans += my_pow(a, MOD - 2, MOD)
print((ans * l)% MOD)
### BUGGY CODE ###

#ないよりも10倍以上早くなる
import sys
input = sys.stdin.readline
 
K,S=map(int,input().split())
if 2<=K<=2500 and 0<=S<=3*K:
    count=0
    Ks=[]
    wa=[]
    for i in range(K+1):
        Ks.append(i)
    X,Y,Z =Ks,Ks,Ks
    for x in X:
        X_=[]
        X_.append(x)
        for y in Y:
            X_Y_=list(X_)
            X_Y_.append(y)
            wa_=sum(X_Y_)
            wa.append(wa_)
    wa= [w for w in wa if w<=S]
    for z in Z:
        for j in wa:
            j+=z
            if j==S:
                count+=1
    print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
K,S=map(int,input().split())
count=0
for x in range(K+1):
    for y in range(K+1):
        if S-(x+y)>=0 and S-(x+y)<=K: count+=1
print(count)
### BUGGY CODE ###

from decimal import Decimal

N,K = map(int,input().split())

prob = Decimal(0)
for i in range(1,N+1):

    for j in range(20):
        if i*2**j >= K:
            prob += Decimal(1/2**j)
            break

print(prob/N)

### FIXED CODE ###

N,K = map(int,input().split())

csum = 0
for i in range(1,N+1):
    c = 0
    flag = 1
    while flag:
        if i*2**c >= K:
            csum += 1/2**c
            flag = 0
        else:
            c += 1
print(csum/N)
### BUGGY CODE ###

def z_argorithm(s):
    s_len=len(s)
    a=[0]*s_len
    a[0]=s_len
    i=1
    j=0
    while i<s_len:
        while i+j<s_len and s[j]==s[i+j]:
            j+= 1
        a[i]=j
        k=1
        if j==0:
            i += 1
            continue
        while i+k<s_len and k+a[k]<j:
            a[i+k]=a[k]
            k+=1

        i +=k
        j -=k
    return a
def main():
    n=int(input())
    s=input()
    ans = 0
    for i in range(n-1):
        a=z_argorithm(s[i:])
        for n,i in enumerate(a):
            if ans < min(n,i):
                ans = min(n,i)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def Z(s):
    """
    s: str
    return list of int with length len(s)
    """
    # initialization
    n=len(s)
    z=[0]*n
    z[0]=n
    # construct
    L,R=0,0
    for i in range(1,n):
        if i>=R: # 過去の結果が全く使えない
            L=R=i
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
        elif z[i-L]<R-i: # 過去の結果が全て使える
            z[i]=z[i-L]
        else: # 過去の結果が一部使える
            L=i
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
    return z
def resolve():
    n=int(input())
    s=input()
    ans=0
    for i in range(n):
        z=Z(s[i:])
        k=len(z) # k=n-i
        for j in range(k):
            ans=max(ans,min(j,z[j]))
    print(ans)
resolve()
### BUGGY CODE ###

input_line=int(input())
ARC = [int(i)for i in input().split()]
ABC = []
count=0
for i in range(10**5):
  AARC = ARC
  AABC = ABC
  for s in ARC:
    if s < i :
      AABC.append(s)
      AARC.remove(s)
      while s in AARC:
        AABC.append(s)
        AARC.remove(s)
  if len(AABC) == len(AARC):
    count+=1

print(count)

### FIXED CODE ###

input_line=int(input())
ARC = [int(i)for i in input().split()]
ARC.sort()
middle = input_line //2
s = ARC[middle]-ARC[middle-1]

print(s)
### BUGGY CODE ###

N=int(input())
A=input().split(" ")
ans=[]
for i in range(1,N+1):
    ans.append(str(A.index(str(i))+1))
print(" ".join(ans))

### FIXED CODE ###

N=int(input())
A=input().split(" ")
ans=[]
for i in range(1,N+1):
    ans.append(0)
for i in range(0,N):
    ans[int(A[i])-1]=str(i+1)
print(" ".join(ans))
### BUGGY CODE ###

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

ans = 0

for i in range(n-1):
    if i == 0:
        q = 0
    else:
        q = a[i-1]
    if i == n-2:
        r = 0
    else:
        r = a[i+2]

    while a[i]+a[i+1] > x:
        if q+a[i] < a[i+1]+r:
            a[i+1] -= 1
            ans += 1
        else:
            a[i] -= 1
            ans += 1

print(ans)

### FIXED CODE ###

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

ans = 0
for i in range(n-1):
    if a[i] > x:
        ans += a[i]-x
        a[i] = x
    if a[i]+a[i+1] > x:
        ans += a[i+1] - (x-a[i])
        a[i+1] = x-a[i]

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

N=int(input())
a=list(map(int,input().split()))
a_=sorted(a,key=lambda x:-x)
ans=0
from collections import Counter
c=Counter(a_)
for i in a_:
    if c[i]==0:
        continue
    c[i]-=1
    for n in range(i):
        if i<2**n:
            t=n
            break
        elif i==2**n:
            t=n+1
            break
    j=2**t-i
    if j in c and c[j]>0:
        ans+=1
        c[j]-=1
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
c = Counter(a)

ans = 0
for i in a:
    if c[i] == 0:
        continue
    c[i] -= 1
    k = 1<<i.bit_length()
    j = k-i
    if j in c and c[j] > 0:
        ans += 1
        c[j] -= 1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

n, m=map(int, input().split())
ab = [["" for _ in range(2)] for _ in range(n)]
for i in range(n):
    temp=list(map(int, input().split()))
    ab[i] = [temp[0],temp[1],False]

sortsecond = lambda val: val[1]

ab.sort(key = sortsecond, reverse = True)
#print(ab)

sum = 0
for dayLeft in range(1, m+1):
#    print(str(dayLeft)+"スタート")
    for i in range(n):
        if((ab[i][0] <= dayLeft) and (ab[i][2] == False)):
            sum += ab[i][1]
#            print(str(ab[i][1])+"を追加")
            ab[i][2] = True
#            print(ab)
            break

print(sum)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import heapq

n, m = map(int, input().split())

work = [[] for _ in range(10**5+1)]
for i in range(n):
    ta, tb = map(int, input().split())
    work[ta].append(tb)

total = 0
cand = []

for d in range(1, m+1):
    for w in work[d]:
        #後で最大値を取り出したいので-1倍して追加
        #（複数の要素も一気にpush）
        heapq.heappush(cand, -w) 
        
    if len(cand) > 0:
        #-1倍して最大値として取得
        total += heapq.heappop(cand)*(-1) 
        
print(total)
### BUGGY CODE ###

N, K = [int(x) for x in input().split(" ")]

if K == 1:
  print(0)
else:
  while N>abs(N-K):
    N = abs(N-K)
  print(N)

### FIXED CODE ###

N, K = [int(x) for x in input().split(" ")]

if N ==0 or K==1 or N == K:
  print(0)
else:
  while N>abs(N-K):
    N = abs(N%K-K)
  print(N)
### BUGGY CODE ###

MOD = 10**9 + 7
N,M = map(int,input().split())
S = [0] + [int(x) for x in input().split()]
T = [0] + [int(x) for x in input().split()]

# 最後に(n,m)でとる
dp = [[0] * (M+1) for _ in range(N+1)]
# 2次元累積和、(n,m) inclusive. 
dp_cum = [[0] * (M+1) for _ in range(N+1)]

# empty
dp[0][0] = 1
dp_cum[0][0] = 1
for n in range(N+1):
  dp_cum[n][0] = 1
for m in range(M+1):
  dp_cum[0][m] = 1
  
for n in range(1,N+1):
  for m in range(1,M+1):
    if S[n] != T[m]:
      dp[n][m] = 0
    else:
      # (n-1, m-1)までで作れてるやつから飛んでくる
      dp[n][m] = dp_cum[n-1][m-1]
    dp_cum[n][m] = dp_cum[n-1][m] + dp_cum[n][m-1] - dp_cum[n-1][m-1] + dp[n][m]
    dp_cum[n][m] %= MOD

#print(dp)
#print(dp_cum)
answer = dp_cum[N][M]
print(answer)


### FIXED CODE ###

MOD = 10**9 + 7
N,M = map(int,input().split())
S = [0] + [int(x) for x in input().split()]
T = [0] + [int(x) for x in input().split()]

# 最後に(n,m)でとる
dp = [[0] * (M+1) for _ in range(N+1)]
# 2次元累積和、(n,m) inclusive. 
dp_cum = [[0] * (M+1) for _ in range(N+1)]

# empty
dp[0][0] = 1
dp_cum[0][0] = 1
for n in range(N+1):
  dp_cum[n][0] = 1
for m in range(M+1):
  dp_cum[0][m] = 1
  
for n in range(1,N+1):
  for m in range(1,M+1):
    if S[n] != T[m]:
      dp[n][m] = 0
    else:
      # (n-1, m-1)までで作れてるやつから飛んでくる
      dp[n][m] = dp_cum[n-1][m-1]
    dp_cum[n][m] = dp_cum[n-1][m] + dp_cum[n][m-1] - dp_cum[n-1][m-1] + dp[n][m]
    dp_cum[n][m] %= MOD

#print(dp)
#print(dp_cum)
answer = dp_cum[N][M]
print(answer)
### BUGGY CODE ###

import copy
N=int(input())
X=list(map(int,input().split()))
Y=copy.deepcopy(X)

Z=N//2
for i in range(N):
    
    Y.pop(i)

    Y.sort()
    
    print(Y[Z-1])
    Y=copy.deepcopy(X)
    

### FIXED CODE ###

import copy
N=int(input())
X=list(map(int,input().split()))
Y=copy.deepcopy(X)
Y.sort()
kiteichiA=Y[N//2-1]
kiteichiB=Y[N//2]
for i in range(N):
    if X[i]>=kiteichiB:
        print(kiteichiA)
    elif X[i]<=kiteichiA:
        print(kiteichiB)
### BUGGY CODE ###

N, M = map(int, input().split())
L = 1000000
dp = [[10000000010 for _ in range(L+1)] for _ in range(N+1)]
W, V = [], []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
dp[0][0] = 0
for i in range(N):
    for j in range(L):
        if j + V[i] <= L:
            dp[i+1][j] = min(dp[i][j], dp[i][j-V[i]] + W[i])
        else:
            dp[i+1][j] = dp[i][j]
for i, d in enumerate(dp[N]):
    if d <= M:
        maxv = i
print(maxv)

### FIXED CODE ###

N, M = map(int, input().split())
L = 100000
dp = [[1000000001 for _ in range(L+1)] for _ in range(N+1)]
W, V = [], []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
dp[0][0] = 0
for i in range(N):
    for j in range(L+1):
        if j - V[i] >= 0:
            dp[i+1][j] = min(dp[i][j], dp[i][j-V[i]] + W[i])
        else:
            dp[i+1][j] = dp[i][j]
for i, d in enumerate(dp[N]):
    if d <= M:
        maxv = i
print(maxv)
### BUGGY CODE ###

n,d,a = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
l.sort()
count = 0
import math
import bisect
i = 0
l1 = []

while i < n:
    sn = i
    s = l[i][0]
    mi = math.ceil(l[i][1]/a)
    count += mi
    l1 =[]
    while i < n and l[i][0] <= s+2*d:
        
        l[i][1] -= mi*a
        if l[i][1] > 0:
            l1.append(i)
        i += 1
        
    if len(l1) > 0:
        i = l1[0]
    else:
        if i == n:
            print(count)
            exit()
    




### FIXED CODE ###

def main():
    n,d,a = map(int,input().split())
    l = [list(map(int,input().split())) for i in range(n)]
    l.sort()
    count = 0
    from collections import deque

    i = 0
    area = deque([])
    damage = deque([])
    total_damage = 0
    count = 0
    ans = 0
    for pos,hp in l:
        while area:
            ar = area[0]
            if ar < pos:
                area.popleft()
                power = damage.popleft()
                total_damage -= power
            else:
                break
        if hp <= total_damage:
            continue
        else:
            count = (hp-total_damage+a-1)//a
            ans += count
            total_damage += count*a
            area.append(pos+2*d)
            damage.append(count*a)

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

from math import gcd

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

def isSetwise(A):
    ret = A[0]
    for a in A:
        ret = gcd(ret, a)
    return ret == 1

def isPairwise(A):
    prd = 1
    for a in A:
        if gcd(a, prd) > 1:
            return False
        prd *= a
    return True

if not isSetwise(A):
    print('not coprime')
    exit()

if isPairwise(A):
    print('pairwise coprime')
else:
    print('setwise coprime')


### FIXED CODE ###

from math import gcd

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

def isSetwise(A):
    ret = A[0]
    for a in A:
        ret = gcd(ret, a)
    return ret == 1
from collections import Counter

def createPrimeList(N):
    isPrime = [True] * (N + 1)
    isPrime[0] = False
    isPrime[1] = False
    smallestPrime = [1] * (N + 1)
    for i in range(2, N + 1):
        if not isPrime[i]:
            continue
        for p in range(i * 2, N, i):
            if isPrime[p]:
                smallestPrime[p] = i
            isPrime[p] = False
    return smallestPrime

from collections import Counter
smallestPrime = createPrimeList(max(A) + 10)
def primeFactorization(N):
    ret = Counter()
    while N > 1:
        p = smallestPrime[N]
        if p == 1:
            ret[N] += 1
            break
        ret[p] += 1
        N //= p
    return ret

def isPairwise(A):
    P = Counter()
    for a in A:
        for p in primeFactorization(a):
            if P[p] >= 1:
                return False
            P[p] += 1
    return True

if not isSetwise(A):
    print('not coprime')
    exit()

if isPairwise(A):
    print('pairwise coprime')
else:
    print('setwise coprime')
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

points = [(i+1, y) for i, y in enumerate(A)]

diff_list = [y - x for x, y in points]
diff_list.sort(reverse=True)

max_b = diff_list[0]
min_b = diff_list[-1]


sadness_list = []
for b in diff_list:
    sadness_list.append(sum([abs(y - (b + x)) for x, y in points]))

print(min(sadness_list))



### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
def calc_sadness(points, b):
    return sum([abs(y - (b + x)) for x, y in points])

points = [(i+1, y) for i, y in enumerate(A)]

# y = x + b
# b = y - x
b_list = [y - x for x, y in points]
b_list.sort(reverse=True)

max_b = b_list[0]
min_b = b_list[-1]

best_ind = len(b_list)//2

minimum = calc_sadness(points, b_list[best_ind])

print(minimum)
### BUGGY CODE ###

import math
from functools import lru_cache


@lru_cache(maxsize=None)
def gcd(a, b):
    return math.gcd(a, b)


K = int(input())

total = 0

for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            total += gcd(gcd(a, b), c)

print(total)


### FIXED CODE ###

import sys
import math
from functools import lru_cache

gcd = [[0] * 201 for _ in range(201)]

for i in range(201):
    for j in range(201):
        gcd[i][j] = math.gcd(i, j)

K = int(input())

total = 0

for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            total += gcd[gcd[a][b]][c]

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

'''
Problem Link - https://atcoder.jp/contests/abc176/tasks/abc176_b
'''
from sys import stdin,stdout
from math import *
from collections import *

mod = 1000000007

def gcd(a,b):
	while b:
		a,b = b,a%b
	return a

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

def set_bits(X):
	c = 0
	while X:
		X &= (X-1);c += 1
	return c

def compute_MOD(N,M): return (N%M + M) % M

def get_array(): return list(map(int, stdin.readline().split()))
 
def get_ints(): return map(int, stdin.readline().split())

def get_int(): return int(stdin.readline())

def get_input(): return stdin.readline().strip()

def main():
	N = get_int()
	Sum = 0
	while N>0:
		rem = N%10
		Sum += rem*10
		N //= 10
	if Sum%9==0:stdout.write('Yes\n')
	else:stdout.write('No\n')

if __name__ == "__main__":
    main()

### FIXED CODE ###

'''
Problem Link - https://atcoder.jp/contests/abc176/tasks/abc176_b
'''
from sys import stdin,stdout
from math import *
from collections import *

mod = 1000000007

def gcd(a,b):
	while b:
		a,b = b,a%b
	return a

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

def set_bits(X):
	c = 0
	while X:
		X &= (X-1);c += 1
	return c

def compute_MOD(N,M): return (N%M + M) % M

def get_array(): return list(map(int, stdin.readline().split()))
 
def get_ints(): return map(int, stdin.readline().split())

def get_int(): return int(stdin.readline())

def get_input(): return stdin.readline().strip()

def main():
	N = get_input()
	Sum = 0
	for i in N:Sum+=int(i)
	if Sum%9==0:stdout.write('Yes\n')
	else:stdout.write('No\n')
	

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

S = input()
#revS = S[::-1]
ls = len(S)
cur_num = 0
cur_r = 0
r = [0]*ls
ans = 0
for i in range(ls):
    if i == 0:
        r[i] = (int(S[ls-i-1])*pow(10,i))%2019
    else:
        r[i] = r[i-1] + (int(S[ls-i-1])*pow(10,i))%2019
        r[i] %= 2019
#print(r)
from collections import Counter
c = Counter(r)

#print(c)
ans = 0
c[0] += 1
for k,v in c.items():
    # if k == 0:
    #     pass
    if v >= 2:
        ans += v*(v-1)//2
print(ans)

### FIXED CODE ###

S = input()
#revS = S[::-1]
ls = len(S)
cur_num = 0
cur_r = 0
r = [0]*ls
ans = 0
for i in range(ls):
    if i == 0:
        r[i] = (int(S[ls-i-1])*pow(10,i,2019))%2019
    else:
        r[i] = r[i-1] + (int(S[ls-i-1])*pow(10,i,2019))%2019
        r[i] %= 2019
#print(r)
from collections import Counter
c = Counter(r)

#print(c)
ans = 0
c[0] += 1
for k,v in c.items():
    # if k == 0:
    #     pass
    if v >= 2:
        ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

'''
☆長さnの数列Aの中央値がxであるとは
１．x以上の要素が (n + 1)// 2 個以上
２．そのようなxの中で最小
ということ。
'''

class BIT:
    def __init__(self, n):
        self.bit = [0] * (n+1)

    def sum(self, i):
        '''
        :param i: 
        :return: bit[i]までの和
        '''
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        '''
        :param i:
        :param x:
        :return: bit[i]にxを加える
        '''
        while i < len(self.bit):
            self.bit[i] += x
            i += i & -i

import numpy as np

def median(L):
    n = len(L)
    L.sort()
    return L[n // 2]

N = int(input())
a = list(map(int, input().split()))
m = min(a)
M = max(a)

med_list= []
for i in range(N):
    for j in range(i + 1, N + 1):
        med_list.append(median(a[i:j]))

def ans_bigger(X):
    '''
    答えがX以上かどうかを判定
    つまり、区間[l. r]のうち中央値がX以上であるものが ((N+1) * N /2 + 1 ) //2 個以上かを判定
    [l, r]の中央値がX以上 =
    '''
    a_X = np.array([1 if a[i] >= X else -1 for i in range(N)]) #1, -1に変換
    cum = np.hstack(([0], np.cumsum(a_X))) #累積和を取る
    min_cum = min(cum)
    cum -= min_cum - 1 #BITを使うために全部0以上に

    b = BIT(max(cum) + 1)
    ans = 0
    for j in range(N + 1):
        ans += b.sum(cum[j])
        b.add(cum[j], 1)
    if ans >= ((N+1) * N /2 + 1 ) //2:
        return True
    else:
        return False

l = min(a)
r = max(a) + 1
#区間[l, r)を2分探索
while r > l + 1:
    if ans_bigger((l + r) // 2):
        l = (l + r) // 2
    else:
        r = (l + r) // 2
print(l)

### FIXED CODE ###

'''
☆長さnの数列Aの中央値がxであるとは
１．x以上の要素が (n + 1)// 2 個以上
２．そのようなxの中で最小
ということ。
'''

class BIT:
    def __init__(self, n):
        self.bit = [0] * (n+1)

    def sum(self, i):
        '''
        :param i: 
        :return: bit[i]までの和
        '''
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        '''
        :param i:
        :param x:
        :return: bit[i]にxを加える
        '''

        while i < len(self.bit):
            self.bit[i] += x
            i += i & -i

'''
def median(L):
    n = len(L)
    L.sort()
    return L[n // 2]
'''

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

def ans_bigger(X):
    '''
    答えがX以上かどうかを判定
    つまり、区間[l. r]のうち中央値がX以上であるものが ((N+1) * N /2 + 1 ) //2 個以上かを判定
    [l, r]の中央値がX以上 =
    '''
    a_X = [1 if a[i] >= X else -1 for i in range(N)]#1, -1に変換
    cum = [N]
    for i in range(N):
        cum.append(cum[i] + a_X[i]) #累積和を取るが、BITを使うため全部0以上に（初項N）
    b = BIT(2 * N + 1)
    ans = 0
    for j in range(N + 1):
        ans += b.sum(cum[j])
        b.add(cum[j], 1)
    if ans >= ((N+1) * N /2 + 1 ) //2:
        return True
    else:
        return False

l = min(a)
r = max(a) + 1
#区間[l, r)を2分探索
while r > l + 1:
    if ans_bigger((l + r) // 2):
        l = (l + r) // 2
    else:
        r = (l + r) // 2
print(l)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
gcds=[]

def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)

for i in range(len(l)):
    omitlist=[l[k] for k in range(len(l))]
    omitlist.pop(i)
    n=len(omitlist)

    if n==1:
        gcds.append(omitlist[0])
    else:
        element = gcd(omitlist[0], omitlist[1])
        if n==2:
            gcds.append(element)
        else:
            for i in range(2,n):
                element=gcd(element,omitlist[i])
            gcds.append(element)

print(max(gcds))

### FIXED CODE ###

n=int(input())
left=list(map(int,input().split()))
right=list(left)
right.reverse()
gcds=[]
gcdleft=[]
gcdright=[]

gcdleft.append(left[0])
gcdright.append(right[0])

def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)

if n==2:
    gcds.append(gcdleft[0])
    gcds.append(gcdright[0])
else:
    for i in range(1,n-1):
        gcdleft.append(gcd(gcdleft[i-1],left[i]))
        gcdright.append(gcd(gcdright[i-1],right[i]))
    gcds.append(gcdright[-1])
    for i in range(0,n-2):
    	gcds.append(gcd(gcdleft[i],gcdright[n-3-i]))
    gcds.append(gcdleft[-1])

print(max(gcds))
### BUGGY CODE ###

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


### FIXED CODE ###

N=int(input())
li=list(map(int,input().split()))
 
m=li[0]
if 0 in li:
  m=0
else:
  for i in range(1,N):
    m=m*li[i]
    if m>10**18:
      m=-1
      break
print(m)
### BUGGY CODE ###

n = int(input())

for i in range(1, 10**9):
    if i % 2 == 0 and i % n == 0: 
        print(i)
        break

### FIXED CODE ###

n = int(input())
if n % 2 != 0:
    print(n*2)
else:
    print(n)
### BUGGY CODE ###

ans = 0
R, G, B, N = map(int, input().split())
for r in range(N//R + 1):
  for g in range(N//G + 1):
    rg = r*R + g*G
    if rg <= N and (N-rg)%B == 0:
      ans += 1
print(ans)

### FIXED CODE ###

ans = 0
R, G, B, N = map(int, input().split())
rl = (N+R-1)//R+1
gl = (N+G-1)//G+1
bl = (N+B-1)//B
for r in range(rl):
  for g in range(gl):
    tmp = N - (r*R) - (g*G)
    if tmp < 0:
      break
    if tmp == 0:
      ans += 1
    elif tmp%B == 0 and tmp%B <= bl:
      ans += 1
print(ans)
### BUGGY CODE ###

#D
from collections import deque
from heapq import heappush, heappop
n,q=map(int,input().split())
data=[[] for i in range(n+1)]
counter=deque([0 for i in range(n+1)])
for i in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
for i in range(q):
    p,x=map(int,input().split())
    counter[p]+=x
h=[1]
done=[]
while h:
    a=heappop(h)
    for i in range(len(data[a])):
        if data[a][i] in done:
            continue
        counter[data[a][i]]+=counter[a]
        heappush(h,data[a][i])
    done.append(a)
counter.popleft()
print(*counter)

### FIXED CODE ###

#D
n,q=map(int,input().split())
data=[[] for i in range(n+1)]
counter=[0]*(n+1)
for i in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
for i in range(q):
    p,x=map(int,input().split())
    counter[p]+=x
h=[1]
done=[0]*(n+1)
while h:
    a=h.pop()
    for l in data[a]:
        if done[l]==0:
            counter[l]+=counter[a]
            h.append(l)
    done[a]=1
print(*counter[1:])