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

N = int(input())
A = [int(input()) for _ in range(N)]

lst = []
for i in range(N):
    flag = False
    for j in range(len(lst)):
        if lst[j] < A[i]:
            lst[j] = A[i]
            lst.sort(reverse = True)
            flag = True
            break
    if flag == False:
        lst.append(A[i])
        lst.sort(reverse = True)

print (len(lst))
            
         

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

dp = [-A[0]]
def solve():
    import bisect
    for i in range(1, N):
        a = bisect.bisect_left(dp, -A[i]+0.1) #入れるべき場所
        # print (a)
        if a == len(dp):
            dp.append(-A[i])
        else:
            dp[a] = -A[i]
        # print (dp)
    return len(dp)


print (solve())
### BUGGY CODE ###

N=int(input())
S=input()
ans=0
for i in range(N-2):
  a=S[i]
  for j in range(i+1,N-1):
    b=S[j]
    for k in range(j+1,N):
      c=S[k]
      if j-i!=k-j and a!=b and a!=c and b!=c:
        ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
ans,r,g,b=0,0,0,0
for s in S:
  if s=='R':
    r+=1
  elif s=='G':
    g+=1
  elif s=='B':
    b+=1
ans=r*g*b
for i in range(N-2):
  a=S[i]
  for j in range(i+1,N-1):
    if 2*j-i>=N:
      break
    b,c=S[j],S[j+j-i]
    if a!=b and b!=c and c!=a:
      ans-=1
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
IND = list(set(A))
# CNT = [A.count(x) for x in IND]
# print(IND)
# print(CNT)
CONB = [A.count(x)*(A.count(x)-1)//2 for x in IND]
# print(CONB)
SUM = sum(CONB)
CALC = [-1]*(N+1)
for i in A:
    if CALC[i] != -1:
        print(CALC[i])
    else:
        # n = CNT[IND.index(i)]
        # ans = SUM - CONB[IND.index(i)] + (n-1)*(n-2)//2
        ans = SUM - A.count(i) + 1
        CALC[i] = ans
        print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
CNT = [0]*(N+1)
# IND = list(set(A))
# CNT = [A.count(x) for x in IND]
for i in A:
    CNT[i] += 1
# print(IND)
# print(CNT)
# CONB = [A.count(x)*(A.count(x)-1)//2 for x in IND]
CONB = [CNT[x]*(CNT[x]-1)//2 for x in range(len(CNT))]
# print(CONB)
SUM = sum(CONB)
for i in A:
    ans = SUM - CNT[i] + 1
    print(ans)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
index = [0] *(N+1)
for i in range(N-2):
  if S[i:i+2] == 'AC':
    index[i] = 1
for _ in range(Q):
  l, r = map(int,input().split())
  print(index[l-1:r-1].count(1))

### FIXED CODE ###

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

from itertools import combinations

n = int(input())
s = input()

comb = combinations(s, 3)
set_ = set()

for x in comb:
    set_.add(x)

print(len(set_))

### FIXED CODE ###

n = int(input())
s = input()

cnt = 0
for x in range(10):
    x_ = str(x)
    for i in range(n-2):
        if s[i] == x_:
            break
    else:
        continue
    for y in range(10):
        y_ = str(y)
        for j in range(i+1, n-1):
            if s[j] == y_:
                break
        else:
            continue
        for z in range(10):
            z_ = str(z)
            for k in range(j+1, n):
                if s[k] == z_:
                    cnt += 1
                    break

print(cnt)
### BUGGY CODE ###



def main():
    N = int(input())

    X = list(map(int, input().split(" ")))

    for i in range(len(X)):
        x = X[:i] + X[i+1:]
        x = sorted(x)

        print(x[len(x)//2])


if __name__ == '__main__':
    main()


### FIXED CODE ###



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

    nums = sorted(X)
    center = len(nums)//2

    dic = {}
    for i,x in enumerate(nums):
        if x not in dic:
            dic[x] = i

    if len(nums)%2 == 0:
        is_even = True
    else:
        is_even = False

    for x in X:
        i = dic[x]
        if is_even:
            if i < center:
                print(nums[center])
            else:
                print(nums[center-1])
        else:
            print(nums[center+1])


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

n=int(input())
a=[]
for i in range(n):
    a.append(int(input())-1)

#TLEチーンコ
i=0
j=0
b=[]
while True:
    j+=1
    if a[i]==1:
        print(j)
        break
    elif a[i] in b:
        print(-1)
        break
    else:
        b.append(i)
        i=a[i]



### FIXED CODE ###

n=int(input())
a=[]
for i in range(n):
    a.append(int(input())-1)
'''
#TLEチーンコ
i=0
j=0
b=[]
while True:
    j+=1
    if a[i]==1:
        print(j)
        break
    elif a[i] in b:
        print(-1)
        break
    else:
        b.append(a[i])
        i=a[i]
'''
i=0
j=0
while True:
    j+=1
    if a[i]==1:
        print(j)
        break
    elif j==n:
        print(-1)
        break
    else:
        i=a[i]
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b_c = [list(map(int,input().split())) for i in range(q)]

for i in range(q):
  b = b_c[i][0]
  c = b_c[i][1]
  for j in range(n):
    if a[j] == b:
      a[j] = c
  print(sum(a))


### FIXED CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b_c = [list(map(int,input().split())) for i in range(q)]

summ = sum(a)
cc = collections.Counter(a)
for i in range(q):
  b = b_c[i][0]
  c = b_c[i][1]
  if b in cc:
    buf = cc[b]
    cc[b] = 0
    if c in cc:
      cc[c] = cc[c] + buf
    else:
      cc[c] = buf
    summ = summ - b*buf + c*buf
    print(summ)
  else:
    print(summ)
### BUGGY CODE ###

a, b, c, d = map(int, input().split())

max = a * c
for i in range(a, b+1):
  for j in range(c, d+1):
    k = i * j
    if k > max:
      max = k
      
print(max)

### FIXED CODE ###

a, b, c, d = map(int, input().split())

e = a * c
f = a * d
g = b * c
h = b * d

list1 = [e, f, g, h]
max = max(list1)
print(max)
### BUGGY CODE ###

def inpl(): return [int(i) for i in input().split()]

H, W = inpl()
ans = max(H, W)
S = ''
for _ in range(H):
    S += input()
T = [[0]*(W-1)]
for i in range(H-1):
    t = []
    for j in range(W-1):
        r = S[i*W+j] + S[i*W+j+1] + S[(i+1)*W+j] + S[(i+1)*W+j+1]
        t.append(r.count('.')%2)
    ts = [0]*(W-1)
    for i, k in enumerate(t):
        if k:
            continue
        ts[i] = T[-1][i] + 1
    T.append(ts)
for iT in T[1:]:
    stack = []
    for i, l in enumerate(iT):
        while stack:
            w, h = stack[-1]
            if h > l:
                dw, dh = stack.pop()
                ans = max(ans, (dh+1)*(i-dw+1))
                continue
            break
        stack.append((i, l))
    while stack:
        dw, dh = stack.pop()
        ans = max(ans, (dh+1)*(i-dw+2))
print(ans)

### FIXED CODE ###

def inpl(): return [int(i) for i in input().split()]

H, W = inpl()
ans = max(H, W)
S = [input() for _ in range(H)]
T = [[0]*(W-1)]
for i in range(H-1):
    t = []
    for j in range(W-1):
        r = S[i][j:j+2] + S[i+1][j:j+2]
        t.append(r.count('.')%2)
    ts = [T[-1][i] + 1 if not k else 0 for i, k in enumerate(t) ]
    T.append(ts)
for iT in T[1:]:
    stack = []
    for i, l in enumerate(iT+[0]):
        dw = -1
        while stack and stack[-1][1] >= l:
            dw, dh = stack.pop()
            ans = max(ans, (dh+1)*(i-dw+1))
        if dw != -1:
            stack.append((dw,l))
            continue
        stack.append((i, l))
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
lst = [[0, 0]] 
for i in range(N):
    lst.append(list(map(int, input().split())))
dp = [[0]*(W+1) for i in range(N+1)]
for i in range(1, N+1):
    for j in range(1, W+1):
        if j - lst[i][0] >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-lst[i][0]]+lst[i][1])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
lst = [[0, 0]] 
for i in range(N):
    lst.append(list(map(int, input().split())))
dp = [[0]*(W+1) for i in range(N+1)]
for i in range(1, N+1):
    for j in range(1, W+1):
        if j - lst[i][0] >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-lst[i][0]]+lst[i][1])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][W])
### BUGGY CODE ###

import itertools
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a_tmp = [0] + list(itertools.accumulate(a))
b_tmp = [0] + list(itertools.accumulate(b))
ans = 0

for i in range(n+1):
    for j in range(m+1):
        if a_tmp[i]+b_tmp[j] <= k:
            ans = max(ans, i+j)
        else:
            break
print(ans)


### FIXED CODE ###

import itertools
import bisect
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a_acc = [0] + list(itertools.accumulate(a))
b_acc = [0] + list(itertools.accumulate(b))
ans = 0

for i in range(n+1):
    if k - a_acc[i] >= 0:
        ans = max(ans, i + bisect.bisect(b_acc, k - a_acc[i])-1)
print(ans)
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N = LI()
    A = LI()

    y = [0] * (10**6 + 1)
    for i in A:
        y[i] += 1

    ans = 0
    for i in A:
        for j in range(1,int(math.sqrt(i)) + 1):
            if j == i and y[i] <= 1: continue
            if j == 1:
                if y[1]: break
                if y[i] > 1 : break
            else:
                if i % j == 0 and (y[j] or y[i//j]):
                    break
        else:
            ans += 1

    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()

    y = [0] * (10**6 + 1)
    z = [0] * (10**6 + 1)
    A = []
    for x in sys.stdin.readline().split():
        x = int(x)
        A.append(x)
        y[x] += 1
        if y[x] == 1:
            c = x * 2
            while c <= 10**6:
                z[c] = 1
                c += x

    ans = 0
    for i in range(N):
        x = A[i]
        if y[x] > 1: continue

        if z[x] == 0:
            ans += 1

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

h,n = map(int,input().split())
li = list(map(int,input().split()))
ls =[]
for i in range(n):
    m = li.index(max(li))
    ls.append(li.pop(m))

if sum(ls) >= h:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

h,n = map(int,input().split())
li = list(map(int,input().split()))
if sum(li) >= h:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

n = int(input())
s = input()

R = []
G = []
B = []

for i in range(n):
    if s[i] == "R":
        R.append(i)
    if s[i] == "G":
        G.append(i)
    if s[i] == "B":
        B.append(i)

dif = 0
for r in R:
    for g in G:
        for b in B:
            if abs(g - r) == abs(g - b):
                dif += 1
            elif abs(b - r) == abs(b - g):
                dif += 1
            elif abs(r - g) == abs(r - b):
                dif += 1
             

print(len(R) * len(G) * len(B) - dif)

### FIXED CODE ###

n = int(input())
s = input()

R_cnt = s.count("R")
G_cnt = s.count("G")
B_cnt = s.count("B")

ans = R_cnt * G_cnt * B_cnt

for i in range(n):
    for d in range(n):
        j = i + d
        k = j + d
        if k >= n: break
        if s[i] != s[j] and s[j] != s[k] and s[i] != s[k]:
            ans -= 1

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

import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 2019

from collections import defaultdict

S = list(input())
dic = defaultdict(int)
dic[0] += 1

ans = 0
x = 0
count = 0
for s in S[::-1]:
    x += int(s) * pow(10, count)
    x %= MOD
    ans += dic[x]
    dic[x] += 1
    count += 1

print (ans)


### FIXED CODE ###

from collections import defaultdict

S = list(input())
N = len(S)

dic = defaultdict(int)
dic[0] = 1

ans = 0

tmp = 0
for i in range(N):
    s = S[N - 1 - i]
    tmp += int(s) * pow(10, i, 2019)
    ans += dic[tmp % 2019]
    dic[tmp % 2019] += 1

print (ans)

# print (dic)
### BUGGY CODE ###

N = int(input())

sum = 0

for i in range(N):
    if i == N-1:
        sum += 0
    else:
        sum += (i+1)%(i+2)

print(sum)


# りゅうせいの解答1　実行時間超過
#  N = int(input())
#
# P_list = []
# M_list = []
#
#
# for i in range(N):
#     if i == N-1:
#         P_list.append(1)
#
#     else:
#         P_list.append(i+2)
#
#
# for i in range(N):
#     M_list.append((i+1) % P_list[i])
#
# print(sum(M_list))

### FIXED CODE ###

N = int(input())

mod_sum = N*(N-1)//2
print(mod_sum)

#りゅうせいの解答2 不正解2つあり
# N = int(input())
#
# mod_sum = int(N*(N-1)/2)
# print(mod_sum)

# りゅうせいの解答1　実行時間超過
#  N = int(input())
#
# P_list = []
# M_list = []
#
#
# for i in range(N):
#     if i == N-1:
#         P_list.append(1)
#
#     else:
#         P_list.append(i+2)
#
#
# for i in range(N):
#     M_list.append((i+1) % P_list[i])
#
# print(sum(M_list))
### BUGGY CODE ###

import sys

H, W, M = map(int, sys.stdin.readline().strip().split())

h = [0] * H
w = [0] * W

g = [[False] * W for _ in range(H)]
S = set()
for _ in range(M):
    Th, Tw = map(int, sys.stdin.readline().strip().split())

    h[Th - 1] += 1
    w[Tw - 1] += 1

    # g[Th - 1][Tw - 1] = True
    S.add((Th - 1, Tw - 1))

max_h = max(h)
max_w = max(w)
ans = max_h + max_w

index_h = [n for n, v in enumerate(h) if v == max_h]
index_w = [n for n, v in enumerate(w) if v == max_w]

sub = 1
# for ih in index_h:
#     for iv in index_w:
#         if g[ih][iv] is False:
#             sub = 0
#             break
#     else:
#         continue
#     break
# ans -= sub
# print(ans)


for ih in index_h:
    for iv in index_w:
        if not (ih, iv) in S:
            print(ans)
            exit()
print(ans - 1)



### FIXED CODE ###

import sys

H, W, M = map(int, sys.stdin.readline().strip().split())

h = [0] * H
w = [0] * W

# g = [[False] * W for _ in range(H)]
S = set()
for _ in range(M):
    Th, Tw = map(int, sys.stdin.readline().strip().split())

    h[Th - 1] += 1
    w[Tw - 1] += 1

    # g[Th - 1][Tw - 1] = True
    S.add((Th - 1, Tw - 1))

max_h = max(h)
max_w = max(w)
ans = max_h + max_w

index_h = [n for n, v in enumerate(h) if v == max_h]
index_w = [n for n, v in enumerate(w) if v == max_w]

sub = 1
# for ih in index_h:
#     for iv in index_w:
#         if g[ih][iv] is False:
#             sub = 0
#             break
#     else:
#         continue
#     break
# ans -= sub
# print(ans)


for ih in index_h:
    for iv in index_w:
        if not (ih, iv) in S:
            print(ans)
            exit()
print(ans - 1)
### BUGGY CODE ###

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

# i-1までのmaxはキャッシュする
m1 = 0
for i in range(n):
  p = a[i - 1]
  if i != 0:
    if m1 < p:
      m1 = p
  
  if i != n - 1:
    c = a[i + 1:]
    cm = max(c)
    if m1 < cm:
      print(cm)
    else:
      print(m1)
  else:
    print(m1)
  
  """
  # 遅すぎる
  b = a.copy()
  del b[i]
  print(max(b))
  # 遅すぎる2
  b = a[0:i]
  c = a[i+1:]
  b += c
  print(max(b))
  """

### FIXED CODE ###

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

# ほとんどは全体のmax?
m1 = max(a)

# max値が多い場合用に2nd max
m2 = sorted(a)[n-2]

for i in range(n):
  if a[i] == m1:
    print(m2)
  else:
    print(m1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

for i in range(2, n):
    if (1, i) in ab and (i, n) in ab: print('POSSIBLE'); exit()
print('IMPOSSIBLE')

### FIXED CODE ###

n, m, *ab = map(int, open(0).read().split())
from_1, to_n = set(), set()
for a, b in zip(*[iter(ab)] *2):
    if a == 1: from_1.add(b)
    if b == n: to_n.add(a)
print('POSSIBLE' if from_1 & to_n else "IMPOSSIBLE")
### BUGGY CODE ###

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

def judge(n):
    j = 0
    for i in range(N):
        if S[i] == n[j]:
            j += 1
        if j == 3:
            return True
    return False

ans = 0

for num in range(1000):
    num = str(num)
    num = "0" * (3-len(num)) + num
    if judge(num):
        ans += 1

print(ans)

### FIXED CODE ###

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

def judge(n):
    j = 0
    for i in range(N):
        if S[i] == n[j]:
            j += 1
        if j == 3:
            return True
    return False

ans = 0

for num in range(1000):
    num = str(num)
    num = "0" * (3-len(num)) + num
    if judge(num):
        ans += 1

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

H,W = map(int,input().split())
s = [[] for i in range(H)]
for i in range(H): s[i] = list(input())
l = [[0]*W for i in range(H)]
r = [[0]*W for i in range(H)]
d = [[0]*W for i in range(H)]
u = [[0]*W for i in range(H)]

for h in range(H):
    if s[h][0] == ".": l[h][0] = 1
    for w in range(1,W):
        if s[h][w] == ".": l[h][w] = l[h][w-1] + 1
    if s[h][W-1] == ".": r[h][W-1] = 1
    for w in range(1,W):
        if s[h][W-1-w] == ".": r[h][W-1-w] = r[h][W-w] + 1

for w in range(W):
    if s[0][w] == ".": d[0][w] = 1
    for h in range(1,H):
        if s[h][w] == ".": d[h][w] = d[h-1][w] + 1
    if s[H-1][w] == ".": u[H-1][w] = 1
    for h in range(1,H):
        if s[H-1-h][w] == ".": u[H-1-h][w] = u[H-h][w] + 1
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, l[h][w]+r[h][w]+u[h][w]+d[h][w]-3)

print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
s = [[] for i in range(H)]
for i in range(H): s[i] = list(input())
l = [[0]*W for i in range(H)]
r = [[0]*W for i in range(H)]
d = [[0]*W for i in range(H)]
u = [[0]*W for i in range(H)]

for h in range(H):
    if s[h][0] == ".": l[h][0] = 1
    for w in range(1,W):
        if s[h][w] == ".": l[h][w] = l[h][w-1] + 1
    if s[h][W-1] == ".": r[h][W-1] = 1
    for w in range(1,W):
        if s[h][W-1-w] == ".": r[h][W-1-w] = r[h][W-w] + 1

for w in range(W):
    if s[0][w] == ".": d[0][w] = 1
    for h in range(1,H):
        if s[h][w] == ".": d[h][w] = d[h-1][w] + 1
    if s[H-1][w] == ".": u[H-1][w] = 1
    for h in range(1,H):
        if s[H-1-h][w] == ".": u[H-1-h][w] = u[H-h][w] + 1
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, l[h][w]+r[h][w]+u[h][w]+d[h][w]-3)

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

s=input()
c=0
while len(s)>1:
  if s[0]==s[len(s)-1]:
    s=s[1:len(s)-1]
  elif s[0]=='x':
    c+=1
    s=s[1:]
  elif s[len(s)-1]=='x':
    c+=1
    s=s[:len(s)-1]
  else:
    print(-1)
    exit()
print(c)

### FIXED CODE ###

s=input()
c=0
while len(s)>1:
  if s[0]==s[len(s)-1]:
    s=s[1:len(s)-1]
  elif s[0]=='x':
    c+=1
    s=s[1:]
  elif s[len(s)-1]=='x':
    c+=1
    s=s[:len(s)-1]
  else:
    print(-1)
    exit()
print(c)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n,s = nm()
a = nl()
mod = 998244353
ans = 0
dp = [[0]*(s+1) for i in range(n+1)]
dp[0][0] = 1
for i,v in enumerate(a):
    dp[i+1][0] = 1
    for j in range(s+1):
        dp[i+1][j] += dp[i][j]
        if j >= v: dp[i+1][j] += dp[i][j-v]
        dp[i+1][j] %= mod
    ans += dp[i+1][s]
print(ans%mod)


### FIXED CODE ###

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n,s = nm()
a = nl()
mod = 998244353
ans = 0
dp = [[0]*(s+1) for i in range(n+1)]
dp[0][0] = 1
for i,v in enumerate(a):
    dp[i+1][0] = 1
    for j in range(s+1):
        dp[i+1][j] += dp[i][j]
        if j >= v: dp[i+1][j] += dp[i][j-v]
        dp[i+1][j] %= mod
    ans += dp[i+1][s]
print(ans%mod)
### BUGGY CODE ###

N=int(input())
A=tuple(map(int,input().split()))
B=list(map(int,input().split()))
from heapq import heappop,heappush
q=[]
a=0
for i,b in enumerate(B):
    heappush(q,(-b,i))
while len(q)>0:
    b,i=heappop(q)
    ba=-b-A[i]
    bb=B[i-1]+B[i+1-N]
    if ba<0:
        a=-1
        break
    elif ba==0:
        continue
    elif -b>bb:
        x=ba//bb
        if x==0:
            a=-1
            break
        B[i]-=bb*x
        heappush(q,(-B[i],i))
        a+=x
    else:
        a=-1
        break
print(a)

### FIXED CODE ###

N=int(input())
A=tuple(map(int,input().split()))
B=list(map(int,input().split()))
from heapq import heappop,heappush
q=[]
a=0
for i,b in enumerate(B):
    heappush(q,(-b,i))
while len(q)>0:
    b,i=heappop(q)
    ba=-b-A[i]
    bb=B[i-1]+B[i+1-N]
    if ba<0:
        a=-1
        break
    elif ba==0:
        continue
    elif -b>bb:
        x,y=divmod(ba,bb)
        if x==0:
            a=-1
            break
        B[i]-=bb*x
        if y>0:
            heappush(q,(-B[i],i))
        a+=x
    else:
        a=-1
        break
print(a)
### BUGGY CODE ###

n,a,b = map(int,input().split())
mod = 10**9+7

# 有理数クラスをインポート
from fractions import Fraction

# 組合せの総数
def comb(n, k):
    
    if n < 0 or k < 0:
        pdt = 0
    
    else:
        pdt = 1
        for s in range(1, k + 1):
            pdt *= Fraction(n - s + 1, s)
    
    # 戻り値をint型にするために分子を取り出す
    return pdt.numerator

print((2**n - 1 - comb(n,a) - comb(n,b)) % mod)

### FIXED CODE ###

def cmb(n, r):
	if n - r < r:
		r = n - r
	if r == 0:
		return 1
	if r == 1:
		return n
	
	num = [n - r + k + 1 for k in range(r)] #numerator(分子)
	den = [k + 1 for k in range(r)] #denominator(分母)
	
	for p in range(2, r + 1):
		pivot = den[p - 1]
		if pivot > 1:
			offset = (n - r) % p
			for k in range(p - 1, r, p):
				num[k - offset] /= pivot
				den[k] /= pivot
	
	result = 1
	for k in range(r):
		if num[k] > 1:
			result *= int(num[k])
			result = result % mod
	
	return result

n,a,b = map(int,input().split())
mod = 10**9+7

print((pow(2,n,mod) - 1 - cmb(n,a) - cmb(n,b)) % mod)
### BUGGY CODE ###

import sys

n, k = map(int, input().split())
P = int(1e9+7)


def cmb(n, r, P):
    r = min(r, n - r)
    inv_y = 1
    for i in range(1, r + 1):
        inv_y = (inv_y * i) % P
    inv_y = pow(inv_y, P - 2, P)
    x = 1
    for i in range(n - r + 1, n + 1):
        x = x * i % P
    return (x * inv_y) % P


if k >= n:
    print(cmb(2*n-1, n, P))
    sys.exit()
if k == 1:
    print((n * n - 1) % P)
    sys.exit()
ans = 0
for i in range(0, k + 1):
    ans = (ans + cmb(n - 1, i, P) * cmb(n, i, P)) % P
print(ans)


### FIXED CODE ###

import sys

n, k = map(int, input().split())
P = int(1e9+7)


def cmb(n, r, P):
    r = min(r, n - r)
    inv_y = 1
    for i in range(1, r + 1):
        inv_y = (inv_y * i) % P
    inv_y = pow(inv_y, P - 2, P)
    x = 1
    for i in range(n - r + 1, n + 1):
        x = x * i % P
    return (x * inv_y) % P


if k >= n:
    print(cmb(2*n-1, n, P))
    sys.exit()
if k == 1:
    print((n * n - 1) % P)
    sys.exit()
ans = 1
comb1 = 1
comb2 = 1
for i in range(1, k + 1):
    iinv = pow(i, P-2, P)
    comb1 = ((comb1 * (n - i)) * (iinv)) % P
    comb2 = ((comb2 * (n - i + 1)) * (iinv)) % P
    ans = (ans + comb1*comb2) % P
print(ans)
### BUGGY CODE ###

from fractions import gcd
#from math import gcd
#import numpy as np

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

lcms=[A[0]]
[lcms.append(s*lcms[-1]//gcd(lcms[-1], s)) for s in A]

sums=[0]
[sums.append( (sums[-1]+lcms[-1]//s) %(10**9+7) )  for s in A]

print(int(sums[-1]))

### FIXED CODE ###

from fractions import gcd
#from math import gcd
import numpy as np
import sys
input = sys.stdin.readline
mod = 10**9+7

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

lcm = 1
for s in A:
    lcm = s*lcm//gcd(lcm, s)

ans = lcm*sum([pow(s, mod-2, mod) for s in A]) % mod
#ans = sum([lcm//s % mod for s in A]) % mod

print(int(ans%mod))
### BUGGY CODE ###

N = input()
A = list(map(int,input().split()))
N = 1
for i in range(len(A)):
    N *= A[i]

if N <= 10**18:
    print(N)
else:
    print(-1)

### FIXED CODE ###

n = input()
A = list(map(int,input().split()))
m = 1

if 0 in A :
    print(0)
    exit()
for i in A:
    m*= i
    if m > 10**18:
        print(-1)
        exit()
print(m)