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

from functools import reduce
import sys
input = sys.stdin.readline

count = int(input())
list = list(map(int, input().split()))
if 0 in list:
    print(0)
else:
    sum = reduce(lambda x, y: x*y, list)
    if sum > 1000000000000000000:
        sum = -1
    print(sum)

### FIXED CODE ###

from functools import reduce
from operator import mul
import sys
input = sys.stdin.readline

count = int(input())
list = list(map(int, input().split()))
sum = list[0]
if 0 in list:
    print(0)
    exit()
else:
    for i in range(count - 1):
        sum = sum * list[i + 1]
        if sum > 1000000000000000000:
            print(-1)
            exit()


    print(sum)
### BUGGY CODE ###

N = int(input())
S = input()
SL = list(S)
cnt = 0
nr = SL.count('R')
ng = SL.count('G')
nb = SL.count('B')
all = nr * ng * nb
cnt = 0
for i in range(len(S)):
    for j in range(i+1,len(S)):
        for k in range(j+1,len(S)):
            if (not (S[i] == S[j] or S[i] == S[k] or S[j] == S[k])) and (j-i) == (k-j):
                cnt += 1
print(all-cnt)

### FIXED CODE ###

N = int(input())
S = input()
SL = list(S)
cnt = 0
nr = SL.count('R')
ng = SL.count('G')
nb = SL.count('B')
ans = nr * ng * nb
cnt = 0
for i in range(len(S)):
    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[k] != S[i]:
            ans -= 1
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]
mod = 10**9+7
SUM = 0

maxA = max(A)
d = 0
while 1:
    if maxA < 2**d:
        break
    d += 1

BitA = [[0]*d for _ in range(N)]
for i in range(N):
    for j in range(d):
        BitA[i][j] = int(bin(A[i]|2**d)[3+j])

BitSumB = 0
for i in range(d):
    tmp = sum([BitA[j][i] for j in range(N)])
    BitSumB += 2 ** (d-i-1) * (tmp * (N - tmp))
    BitSumB = BitSumB % mod

print(BitSumB)


### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]
mod = 10**9+7
SUM = 0

maxA = max(A)
d = 0
while 1:
    if maxA < 2**d:
        break
    d += 1

BitSumB = 0
for i in range(d):
    tmp = 0
    for n in range(N):
        tmp += (A[n] >> i) & 1
    BitSumB += (2**i) * tmp * (N - tmp)



"""
BitA = [[0]*d for _ in range(N)]
for i in range(N):
    BitA[i] = list(map(int, format(bin(A[i])[2:], '0>{}'.format(d))))

BitSumB = 0
for i in range(d):
    tmp = sum([BitA[j][i] for j in range(N)])
    BitSumB += 2 ** (d-i-1) * (tmp * (N - tmp))
    #BitSumB = BitSumB % mod
"""

print(BitSumB % mod)
### BUGGY CODE ###

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

b=[0]*(N+1)
for b0 in range(2*a[0]+1):
    b[0] = b0
    for i in range(1,N+1):
        b[i] = 2*a[i-1] - b[i-1]
    if b[0] == b[N]: break
print(*b[:N])

### FIXED CODE ###

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

b=[0]*(N+1)
b[0] = sum(a)-2*sum(a[1::2])
for i in range(1,N+1):
    b[i] = 2*a[i-1] - b[i-1]
print(*b[:N])
### BUGGY CODE ###

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

dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = i + 1
mod = 998244353

ans = 0
for i in range(n):
    for j in range(s+1):
        if s > j > 0:
            dp[i+1][j] += dp[i][j]
        if j + a[i] <= s:
            dp[i+1][j+a[i]] += dp[i][j]
            dp[i+1][j+a[i]] %= mod

    ans += dp[i+1][s] * (n - i)
    ans %= mod

print(ans)

### FIXED CODE ###

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

dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = i + 1
mod = 998244353

ans = 0
for i in range(n):
    for j in range(s+1):
        if s > j > 0:
            dp[i+1][j] += dp[i][j]
        if j + a[i] <= s:
            dp[i+1][j+a[i]] += dp[i][j]
            dp[i+1][j+a[i]] %= mod

    ans += dp[i+1][s] * (n - i)
    ans %= mod

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

def telepo_test(start, goal, delta, board):
    route = [start + delta * i for i in range(abs(goal - start) // abs(delta) + 1)]
    route = [board[r] for r in route]

    mp = 0
    for s, t in zip(route[:-1], route[1:]):
        mp += abs(t[0] - s[0]) + abs(t[1] - s[1])
    return mp


H, W, D = tuple(map(int, input().split()))
board = dict()
for h in range(H):
    row = tuple(map(int, input().split()))
    for w in range(W):
        board[row[w]] = (h, w)
Q = int(input())

LRs = [tuple(map(int, input().split())) for _ in range(Q)]
result = [telepo_test(LR[0], LR[1], D, board) for LR in LRs]

for r in result:
    print(r)


### FIXED CODE ###

def telepo_test(start, goal, delta, board):
    route = [start + delta * i for i in range(abs(goal - start) // abs(delta) + 1)]
    route = [board[r] for r in route]

    mp = 0
    for s, t in zip(route[:-1], route[1:]):
        print(s,t)
        mp += abs(t[0] - s[0]) + abs(t[1] - s[1])
    return mp


H, W, D = tuple(map(int, input().split()))
board = dict()
for h in range(H):
    row = tuple(map(int, input().split()))
    for w in range(W):
        board[row[w]] = (h, w)
delta = dict([(i, 0) for i in range(1, D+1)])
for d in range(D+1, H*W+1):
    delta[d] = delta[d-D] + abs(board[d][0] - board[d-D][0]) + abs(board[d][1] - board[d-D][1])

Q = int(input())

LRs = [tuple(map(int, input().split())) for _ in range(Q)]
result = [delta[LR[1]] - delta[LR[0]] for LR in LRs]

for r in result:
    print(r)
### BUGGY CODE ###

import numpy as np

N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 1000000007
numbers = S[:]
numbers.sort()


dp = np.zeros((N+1, X+1), dtype=np.int64)
dp[0] = [x for x in range(X+1)]


for i, n  in enumerate(numbers):
    for x in range(X+1):
        dp[i+1][x] += dp[i][x % n]
        dp[i+1][x] += dp[i][x] * i 

print(int(dp[N][X] % MOD))


### FIXED CODE ###

N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 1000000007
numbers = S[:]
numbers.sort(reverse=True)


dp = {X: 1}

for i, n in enumerate(numbers):
    tmp_dp = {}
    for k, v in dp.items():
        if k < n:
            tmp_dp[k] = (tmp_dp.get(k,0)+v*(N-i))
        else:
            tmp_dp[k]=(tmp_dp.get(k,0)+v*(N-i-1)) 
            tmp_dp[k%n]=(tmp_dp.get(k%n,0)+v) 
    dp = tmp_dp.copy()
        
ans = 0
for k, v in dp.items():
    ans += k *  v

print(ans % MOD)
### BUGGY CODE ###

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

for i in range(n):
    z = y.copy()
    z.remove(x[i])
    print(z[n//2 -1])

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
y = sorted(x)
a = y[n//2 - 1]
b = y[n//2]

for i in range(n):
    if x[i] >= b:
        print(a)
    else:
        print(b)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7
ans = 0
for k in range(60):
    A_0 = 0
    A_1 = 0
    for i in range(N):
        if A[i]>>k&1:
            A_1 += 1
        else:
            A_0 += 1
    num = A_1 * A_0
    ans += (num * 2 ** k)
ans %=  mod
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7
ans = 0
for k in range(60):
    A_0 = 0
    A_1 = 0
    for i in range(N):
        if A[i]>>k&1:
            A_1 += 1
        else:
            A_0 += 1
    num = A_1 * A_0
    ans += (num * 2 ** k)
ans %=  mod
print(ans)
### BUGGY CODE ###

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

dice = list(map(int, input().split()))
a = 0
b = 0

a = sum(dice[0: k])
b = sum(dice[0: k])

res = 0
ll = 0
s = 0
for i in range(k, len(dice)):
    a += dice[i]
    a -= dice[s]
    if a > b:
        b = a
        ll = i
    s += 1

for mn in range(ll - k + 1, ll + 1):
    ss = range(dice[mn] + 1)
    res += sum(ss) / dice[mn]
print(res)

### FIXED CODE ###

n, k = map(int, input().split())
 
dice = list(map(int, input().split()))
 
a = sum(dice[0: k])
b = sum(dice[0: k])
 
res = 0
ll = 0
s = 0

for i in range(k, len(dice)):
    a += dice[i]
    a -= dice[i - k]
    if a > b:
        b = a
 
res = (b + k) /2.0
 
print(res)
### BUGGY CODE ###

import math

N,M = (int(i) for i in input().split())
a = [0] * M
mod = 1000000007
for i in range(M):
    a[i] = int(input())

def calc(f,t):
    tmp = t - f
    i = 1
    ans = 1
    if tmp == 1:
        return 1
    if tmp == 0:
        return 1
    while(tmp >= 2*i):
        ans += math.factorial(tmp - i) // math.factorial(i) // math.factorial(tmp - 2*i)
        i += 1
    return ans

flag = 0
A = 1
if M > 0:
    A *= calc(0,a[0]-1)

for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        flag = 1
        break
    A *= calc(a[i]+1,a[i+1]-1)
    A %= mod

if M > 0:
    A *= calc(a[M-1]+1,N)
    A %= mod

if flag == 1:
    print(0)
elif M == 0:
    print(calc(0,N))
else:
    print(A)


### FIXED CODE ###


N,M = (int(i) for i in input().split())
a = [0] * M
mod = 1000000007
for i in range(M):
    a[i] = int(input())
a.append(100000000)
flag = 0
for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        flag = 1
        break

dp = [1] * (N + 1)
tmp = 0

for i in range(N-1):
    if i+1 == a[tmp]:
        dp[i+2] = dp[i]
    elif i == a[tmp]:
        dp[i+2] = dp[i+1]
        tmp += 1
    else:
        dp[i+2] = (dp[i+1] + dp[i]) % mod

if flag == 1:
    print(0)
else:
    print(dp[N])
### BUGGY CODE ###

import bisect as bc
from collections import defaultdict
from collections import deque
N = int(input())
A = list(map(int,input().split()))
A.sort()
q = set([i for i in range(N)])
 
for i in range(N):
    ai = A[i]
    itr = list(q)
    for j in itr:
        if j == i:
            continue
        if A[j] % ai == 0:
            q.remove(j)
 
print(len(q))
 
 

### FIXED CODE ###

import bisect as bc

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

dp = [True for _ in range(A[-1]+1)]

for i in range(N):
    ai = A[i]
    for j in range(2,A[-1]+1):
        if ai*j > A[-1]:
            break
        if dp[ai*j]:
            dp[ai*j] = False

ans = 0
finish = [True for _ in range(A[-1]+1)]
for i in range(N):
    if dp[A[i]] and finish[A[i]]:
        if bc.bisect_right(A,A[i]) - bc.bisect_left(A,A[i]) == 1:
            ans += 1
            finish[A[i]] = False

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

n = int(input())
lst = list(map(int, input().split()))
flag = 0
for i in range(n):
  for j in range(i):
    if lst[i] == lst[j]:
      print('NO')
      flag = 1
      break
  if flag == 1:
    break
  if i == n-1:
    flag = 2
if flag == 2:
  print('YES')

### FIXED CODE ###

n = int(input())
lst = list(map(int, input().split()))
flag = 0
lst.sort()
for i in range(n-1):
  if lst[i] == lst[i+1]:
    print('NO')
    flag = 1
    break
if flag == 0:
  print('YES')
### BUGGY CODE ###

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

    result = 0
    bs = [0] * N
    for b in range(60):
        a = [(e >> b) & 1 for e in A]
        bs[N - 1] = a[N - 1]
        t = bs[N - 1]
        for i in range(N - 2, -1, -1):
            t += a[i]
            bs[i] = t

        t = 0
        for i in range(N - 1):
            if a[i] == 0:
                t += bs[i + 1]
            else:
                t += (N - (i + 1)) - bs[i + 1]
        result = (result + t * (1 << b)) % 1000000007
    print(result)
main()


### FIXED CODE ###

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

    r = list(range(N - 2, -1, -1))
    result = 0
    for b in range(60):
        t = 0
        bs = (A[N - 1] >> b) & 1
        for i in r:
            if (A[i] >> b) & 1 == 0:
                t += bs
            else:
                t += (N - (i + 1)) - bs
                bs += 1
        result = (result + t * (1 << b)) % 1000000007
    print(result)
main()
### BUGGY CODE ###

import copy

V, M = map(int, input().split())
d = [0] * V
prev = [0] * V
INF = float('inf')

cost = [[INF] * V for i in range(V)]
for i in range(M):
    a, b, c = map(int,  input().split())
    cost[a - 1][b - 1] = c
    cost[b - 1][a - 1] = c
    
def dijkstra_back(s,t):
    prev = [s] * V
    d = [float("inf")] * V
    used = [False] * V
    d[s] = 0
    
    while True:
        v = -1
        for i in range(V):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
        
        for i in range(V):
            if d[i] > d[v] + cost[v][i]: 
                d[i] = d[v] + cost[v][i]
                prev[i] = v
        
    path = [t]
    while prev[t] != s:
        path.append(prev[t])
        prev[t] = prev[prev[t]]
    path.append(s)
    path = path[::-1]
    return path

cost2 = copy.deepcopy(cost)
for i in range(V - 1):
    for j in range(i + 1, V):
        g = dijkstra_back(i, j)
        for k in range(len(g) - 1):
            cost2[g[k]][g[k + 1]] = INF
            cost2[g[k + 1]][g[k]] = INF
            
cnt = 0
for i in range(V):
    for j in range(V):
        if cost2[i][j] != INF:
            cnt += 1
                     
print(cnt // 2)

### FIXED CODE ###

import copy
from scipy.sparse.csgraph import floyd_warshall as wf

N, M = map(int, input().split())
INF = float('inf')

d = [[INF] * (N) for i in range(N)]
e_list = []
for i in range(N):
    d[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    d[a - 1][b - 1] = c
    d[b - 1][a - 1] = c
    e_list.append([a - 1, b - 1, c])
    
wf = wf(d)

cnt = M
for a, b, c in e_list:
    for i in range(N):
        if wf[i][a] + c == wf[i][b]:
            cnt -= 1
            break
    
print(cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


MOD = 10 ** 9 + 7


def modFact(n):
    global MOD
    if n == 1:
        return 1
    else:
        return (n * modFact(n - 1)) % MOD


def modInvFact(n):
    global MOD
    ans = 1
    for i in range(1, n + 1):
        ans *= pow(i, MOD - 2, MOD)
        ans %= MOD
    return ans


def modCombi(n, r):
    global MOD
    if r == 0:
        return 1
    else:
        N = modFact(n)
        NR = modInvFact(n - r)
        R = modInvFact(r)
    return (N * R * NR) % MOD


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

for i in range(1, K + 1):
    A = modCombi(K - 1, i - 1)
    if N - K < i - 1:
        B = 0
    else:
        B = modCombi(N - K + 1, i)
    print((A * B) % MOD)


### FIXED CODE ###

MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    factorials = [0] * (n + 1)
    factorials[0] = 1
    for i in range(n):
        factorials[i + 1] = (factorials[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(factorials[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return factorials, invs


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

factorials, invs = prepare(N)

for i in range(1, K + 1):
    A = factorials[K - 1] * invs[i - 1] * invs[K - i] % MOD
    if N - K < i - 1:
        B = 0
    else:
        B = factorials[N - K + 1] * invs[i] * invs[N - K + 1 - i] % MOD
    print((A * B) % MOD)
### BUGGY CODE ###

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

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

print(sum(a))

### FIXED CODE ###

import heapq
import math

n, m = map(int, input().split())
a = [-1*int(x) for x in input().split()]
heapq.heapify(a)
 
for _ in range(m):
    min_a = heapq.heappop(a)
    heapq.heappush(a, math.ceil(min_a / 2))
    
print(sum(a)*(-1))
### BUGGY CODE ###

s = input()
dp = [[0 for i in range(13)] for i in range(len(s))]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1
d = [1]
for i in range(1,len(s)):
    d.append(d[i-1]*10 % 13)
    
for i in range(1,len(s)):
    for r in range(13):
        if s[-(i+1)] == "?":
            for k in range(10): 
                dp[i][(k * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)
                
        else:
            dp[i][(int(s[-(i+1)]) * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)

print(dp[len(s)-1][5]%(10**9+7))


### FIXED CODE ###

s = input()
dp = [[0 for i in range(13)]]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1
        
d = [1]   
for i in range(1,len(s)):
    dp.append([0]*13)
    d.append(d[i-1]*10 % 13)
    for r in range(13):
        if s[-(i+1)] == "?":
            for k in range(10): 
                dp[i][(k * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)
                
        else:
            dp[i][(int(s[-(i+1)]) * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)

print(dp[len(s)-1][5]%(10**9+7))
### BUGGY CODE ###

from scipy.sparse import*
i=lambda:map(int,input().split())
f=csgraph.floyd_warshall
n,m,l=i()
d=eval('[0]*-~n,'*-~n)
exec('a,b,c=i();d[a][b]=c;'*m)
d=f(f(d,0)<=l)
d[d>9e9]=0
q,=i()
exec('s,t=i();print(int(d[s,t])-1);'*q)

### FIXED CODE ###

from scipy.sparse import*
s=csgraph.floyd_warshall
n,m,l,*t=map(int,open(0).read().split())
d=eval('[9e9]*-~n,'*-~n)
for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=d[b][a]=c
d=s(d)
d[d>l]=9e9
d[d<=l]=1
d=s(d)
d[d>9e9]=9e9
for s,t in zip(*[iter(t[m*3+1:])]*2):print(int(d[s,t]%9e9-1))
### BUGGY CODE ###

def solve(n, a, b):
  ab = [(ai, bi) for ai, bi in zip(a, b) if ai < bi]
  dp = [[j for j in range(n+1)] for i in range(len(ab)+1)]
  for i, (ai, bi) in enumerate(ab, 1):
    for j in range(n+1):
      if j >= ai:
        dp[i][j] = max(dp[i-1][j], dp[i][j-ai]+bi)
      else:
        dp[i][j] = dp[i-1][j]
  return dp[-1][-1]  

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

N = solve(N, A, B)
N = solve(N, B, A)
print(N)

### FIXED CODE ###

def solve(n, a, b):
  ab = [(ai, bi) for ai, bi in zip(a, b) if ai < bi]
  if len(ab) == 0:
    return n
  elif len(ab) == 1:
    a0, b0 = ab[0]
    return (n//a0)*b0 + n%a0
  elif len(ab) == 2:
    (a0, b0), (a1, b1) = ab
    if b0/a0 < b1/a1:
      a0, b0, a1, b1 = a1, b1, a0, b0
    return max(((n-a1*i)//a0)*b0 + (n-a1*i)%a0 + i*b1 for i in range(a0))
  else:
    dp = [j for j in range(n+1)]
    for ai, bi in ab:
      for j in range(ai, n+1):
        dp[j] = max(dp[j], dp[j-ai]+bi)
    return dp[-1]

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

N = solve(N, A, B)
N = solve(N, B, A)
print(N)
### BUGGY CODE ###

import copy
import sys
sys.setrecursionlimit(10000000)

f_inf = float("inf")

N, M, P = map(int, input().split())
ABC_d = {}
for m in range(M):
    A, B, C = map(int, input().split())
    if A in ABC_d:
        ABC_d[A].append([B, C - P])
    else:
        ABC_d[A] = [[B, C - P]]

cost = [-f_inf] * N
# cost = np.empty(N, dtype = int) - f_inf
cost[0] = 0

# def solve(pos, already):
#     global cost
#     global already2

#     if not(pos in ABC_d): return

#     for B, C in ABC_d[pos]:
#         if already[B - 1] == True:
#             if cost[B - 1] == f_inf:
#                 pass
#             elif cost[pos-1] == f_inf or cost[B - 1] < cost[pos - 1] + C:
#                 cost[B-1] = f_inf
#                 solve(B, already)
#         elif cost[B - 1] < cost[pos - 1] + C:
#             cost[B - 1] = cost[pos - 1] + C
#             already2 = already[:]
#             already2[B - 1] = True
#             solve(B, already2)

def solve(pos, cnt):
    global cost

    if not(pos in ABC_d): return
    if cnt > N: cost[pos-1] = f_inf;
    # print (pos, cnt, N, cost[pos - 1])
    for B, C in ABC_d[pos]:
        # print (cost[B - 1], cost[pos - 1] + C)
        if cost[B - 1] == f_inf or cost[B - 1] >= cost[pos - 1] + C:
            pass
        elif cost[pos-1] == f_inf:
            cost[B-1] = f_inf
            solve(B, cnt + 1)
        elif cost[B - 1] < cost[pos - 1] + C:
            cost[B - 1] = cost[pos - 1] + C
            solve(B, cnt + 1)


# already = np.zeros(N, dtype = bool)
already = [False] * N
already[0] = True
solve(1, 1)

if (cost[-1] == f_inf):
    print (-1)
else:
    print (max(0, int(cost[-1])))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)

f_inf = sys.maxsize

N, M, P = map(int, input().split())
ABC_d = {}
for m in range(M):
    A, B, C = map(int, input().split())
    if A in ABC_d:
        ABC_d[A].append([B, C - P])
    else:
        ABC_d[A] = [[B, C - P]]

cost = [-f_inf] * N
cost[0] = 0

def solve(pos, cnt):
    global cost

    if not(pos in ABC_d): return
    if cnt > N: cost[pos-1] = f_inf;

    for B, C in ABC_d[pos]:
        if cost[B - 1] == f_inf or cost[B - 1] >= cost[pos - 1] + C:
            pass
        elif cost[pos-1] == f_inf:
            cost[B-1] = f_inf
            solve(B, cnt + 1)
        elif cost[B - 1] < cost[pos - 1] + C:
            cost[B - 1] = cost[pos - 1] + C
            solve(B, cnt + 1)

solve(1, 1)

if (cost[-1] == sys.maxsize):
    print (-1)
else:
    print (max(0, int(cost[-1])))
### BUGGY CODE ###

import math

n = int(input())

ans = []

def n2divide(n):
    for i in range(1, n):
            if n % i == 0:
                ans.append(i + n/i -2)   
    return ans
    
    
a = n2divide(n)
print(int(min(a)))

### FIXED CODE ###

import math

n = int(input())

array = []
ans = []

def n2divide(n):
    for i in range(1, int(math.sqrt(n))+1):
            if n % i == 0:
                array.append(i)
                
    for j in array:
        ans.append(j + n/j -2)
        
    return ans
    
    
a = n2divide(n)
print(int(min(a)))
### BUGGY CODE ###

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

count = 1
for i in range(1,N):
    for p in range(i):
        if P[p] < P[i]:
            break
    else:
        count += 1

print(count)

### FIXED CODE ###

def main():
    N = int(input())
    P = list(map(int,input().split()))
    min_val = 2*10e5
    count = 1
    for i in range(1,N):
        if min_val > P[i-1]:
            min_val = P[i-1]
        if P[i] <= min_val:
            count += 1
    print(count)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]


left = [[0]*W for _ in range(H)]
right = [[0]*W for _ in range(H)]
top = [[0]*W for _ in range(H)]
bottom = [[0]*W for _ in range(H)]

for j in range(W):
    cnt = 0
    for i in range(H):
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
            top[i][j] = cnt
            
for j in range(W):
    cnt = 0
    for i in reversed(range(H)):
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
            bottom[i][j] = cnt
            
for i in range(H):
    cnt = 0
    for j in range(W):
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
            left[i][j] = cnt
            
for i in range(H):
    cnt = 0
    for j in reversed(range(W)):
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
            right[i][j] = cnt
                        
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans,left[i][j]+right[i][j]+top[i][j]+bottom[i][j]-3)
        
print(ans)

            

### FIXED CODE ###

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]


left = [[0]*W for _ in range(H)]
right = [[0]*W for _ in range(H)]
top = [[0]*W for _ in range(H)]
bottom = [[0]*W for _ in range(H)]

for j in range(W):
    cnt = 0
    for i in range(H):
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
            top[i][j] = cnt
            
for j in range(W):
    cnt = 0
    for i in reversed(range(H)):
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
            bottom[i][j] = cnt
            
for i in range(H):
    cnt = 0
    for j in range(W):
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
            left[i][j] = cnt
            
for i in range(H):
    cnt = 0
    for j in reversed(range(W)):
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
            right[i][j] = cnt
                        
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans,left[i][j]+right[i][j]+top[i][j]+bottom[i][j]-3)
        
print(ans)
### BUGGY CODE ###

L,R = map(int,input().split())
mi = 2018
for i in range(R-L):
  for j in range(R-L):
    mi = min(mi,(L+i)*(L+j+1)%2019)
    if mi == 0:
      break
print(mi)

### FIXED CODE ###

L,R = map(int,input().split())
mi = 2018
break_loop = False
for i in range(R-L):
  for j in range(R-L):
    mi = min(mi,(L+i)*(L+j+1)%2019)
    if mi == 0:
       break_loop = True
       break
  if break_loop:
    break
print(mi)