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

aa, bb = map(int, input().split())
A = max(aa, bb)
B = min(aa, bb)


def get_max(a, b):
    while True:
        c = a % b
        if c == 0:
            return b
        a = b
        b = c


B = get_max(A, B)

temp = []
for i in range(1, B + 1):
    if B % i == 0:
        temp.append(i)

flag = [0] * len(temp)
count = len(temp)
for i in range(0, len(temp)):
    for j in range(i + 1, len(temp)):
        if flag[j] == 0:
            max_ = get_max(temp[i], temp[j])
            if max_ != 1:
                flag[j] = 1
                count -= 1

print(count)


### FIXED CODE ###

aa, bb = map(int, input().split())
A = max(aa, bb)
B = min(aa, bb)


def get_max(a, b):
    while True:
        c = a % b
        if c == 0:
            return b
        a = b
        b = c


def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct


B = get_max(A, B)
factors = factorize(B)

if len(factors) == 0:
    print(1)
else:
    count = 1
    for i in range(0, len(factors) - 1):
        if factors[i] != factors[i + 1]:
            count += 1
    print(count + 1)
### BUGGY CODE ###

from collections import deque
import sys

def input():
    return sys.stdin.readline().strip()

def main():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Dh,Dw = map(int,input().split())
    S = [list(input()) for _ in range(H)]
    S[Ch-1][Cw-1] = 0

    def bfs(x,y):
        que = deque()
        que.append((x,y))

        while que:
            x,y = que.popleft()
            for dx in range(-2,3):
                for dy in range(-2,3):
                    sx = x + dx
                    sy = y + dy
                    if sx < 0 or sx >= W or sy < 0 or sy >= H:
                        continue
                    if S[sy][sx] == '#':
                        continue
                    if (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1)):
                        cnt = 0
                    else:
                        cnt = 1
                    if S[sy][sx] == '.':
                        que.append((sx,sy))
                        S[sy][sx] = S[y][x] + cnt
                    elif S[sy][sx] > S[y][x] + cnt:
                        S[sy][sx] = S[y][x] + cnt
                        que.append((sx,sy))
    bfs(Cw-1,Ch-1)
    print(S[Dh-1][Dw-1] if S[Dh-1][Dw-1] != '.' else '-1')

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
import sys

def input():
    return sys.stdin.readline().strip()

def main():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Dh,Dw = map(int,input().split())
    S = [list(input()) for _ in range(H)]
    S[Ch-1][Cw-1] = 0

    def bfs(x,y):
        que = deque()
        que.append((x,y))

        while que:
            x,y = que.popleft()
            for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
                sx = x + dx
                sy = y + dy
                if sx < 0 or sx >= W or sy < 0 or sy >= H:
                    continue
                if S[sy][sx] == '#':
                    continue
                if S[sy][sx] == '.':
                    S[sy][sx] = S[y][x]
                    que.appendleft((sx,sy))        
                else:
                    if S[sy][sx] > S[y][x]:
                        S[sy][sx] = S[y][x]
                        que.appendleft((sx,sy)) 
            for dx in range(-2,3):
                for dy in range(-2,3):
                    if (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1),(0,0)):
                        continue
                    sx = x + dx
                    sy = y + dy
                    if sx < 0 or sx >= W or sy < 0 or sy >= H:
                        continue
                    if S[sy][sx] == '#':
                        continue
                    if S[sy][sx] == '.':
                        S[sy][sx] = S[y][x] + 1
                        que.append((sx,sy))
                    else:
                        if S[sy][sx] > S[y][x] + 1:
                            S[sy][sx] = S[y][x] + 1
                            que.append((sx,sy))     
    bfs(Cw-1,Ch-1)
    print(S[Dh-1][Dw-1] if S[Dh-1][Dw-1] != '.' else '-1')

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

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

candidate1 = []
candidate = {}
for i in range(N):
    if i == 0:
        candidate1 = make_divisors(A[i])
    elif i == 1:
        candidate2 = make_divisors(A[i])
        prev = -1
        for c in sorted(candidate1 + candidate2):
            if c != prev and prev != -1 and candidate[prev]['atari'] < 2:
                candidate[prev]['hazure'] += 1
            if c not in candidate:
                candidate[c] = {
                    'atari': 1,
                    'hazure': 0
                }
            else:
                candidate[c]['atari'] += 1
            prev = c
        if candidate[prev]['atari'] < 2:
            candidate[prev]['hazure'] += 1            
    else:
        delete_key = []
        for c in candidate.keys():
            if A[i] % c == 0:
                candidate[c]['atari'] += 1
            else:
                if candidate[c]['hazure'] > 0:
                    delete_key.append(c)
                else:
                    candidate[c]['hazure'] += 1
        for d in delete_key:
            del candidate[d]
print(max(candidate.keys()))

### FIXED CODE ###

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

candidate1 = []
candidate = {}
for i in range(N):
    if i > 1:
        delete_key = []
        for c in candidate.keys():
            if A[i] % c == 0:
                candidate[c]['atari'] += 1
            else:
                candidate[c]['hazure'] += 1        
    elif i == 0:
        candidate1 = make_divisors(A[i])
    elif i == 1:
        candidate2 = make_divisors(A[i])
        prev = -1
        for c in sorted(candidate1 + candidate2):
            if c != prev and prev != -1 and candidate[prev]['atari'] < 2:
                candidate[prev]['hazure'] += 1
            if c not in candidate:
                candidate[c] = {
                    'atari': 1,
                    'hazure': 0
                }
            else:
                candidate[c]['atari'] += 1
            prev = c
        if candidate[prev]['atari'] < 2:
            candidate[prev]['hazure'] += 1            
max = 0
for c in candidate:
    if candidate[c]['hazure'] < 2 and max < c:
        max = c
print(max)
### BUGGY CODE ###

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

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

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

now_lcm = A[0]
for a in A[1:]:
  now_lcm = lcm(now_lcm, a)

MOD = 1000000000 + 7
ans = 0
for a in A:
  ans = (ans + (now_lcm//a)) % MOD
print(ans)

### FIXED CODE ###

import fractions
MOD = 1000000000+7

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

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

a_lcm = A[0]
for a in A[1:]:
  a_lcm = lcm(a_lcm, a)

ans = 0
for a in A:
  ans += a_lcm//a
print(ans%MOD)
### BUGGY CODE ###

a = int(input())
l = input()
dp = [0]*1010
#print('###############')
def bfs(i,x,y):
	if y == 3:
		dp[int(x)] = 1
	else:
		for j in range(i,a):
			bfs(j+1,x+str(l[j]),y+1)
bfs(0,'',0)
print(sum(dp))

### FIXED CODE ###

a = int(input())
b = input()
ans = 0
for i in range(1000):
	T = '0'*(3-len(str(i)))
	t = T+ str(i)
	I = 0
	while I < 3:
		for j in b:
			#if t == '022':print(I,t[I],j)
			if I == 3:
				break
			if t[I] == j:I+=1
			#if t == '022':print(I,j)
		
		if I == 3: 
			#print(t)
			ans +=1
		break
print(ans)
### BUGGY CODE ###

from collections import defaultdict

N,Q=map(int,input().split())
l=[ tuple( map(int,input().split()) ) for i in range(N-1) ]
p=[ tuple( map(int,input().split()) ) for i in range(Q) ]
d=defaultdict(list)
for vert,childs in l:
    d[vert].append(childs)

for i in range(N,0,-1):
    for j in d[i]:
        if j in d.keys():
            for x in d[j]:
                d[i].append(x)

d_2=defaultdict(int)
for i in range(1,N+1):
    d_2[i]=0

for p,x in p:
    d_2[p]+=x
    for o in d[p]:
        d_2[o]+=x

ans=d_2.values()
print(*ans)

### FIXED CODE ###

from collections import defaultdict

N,Q=map(int,input().split())
l=[ tuple( map(int,input().split()) ) for i in range(N-1) ]
p=[ tuple( map(int,input().split()) ) for i in range(Q) ]
d=defaultdict(list)
for vert,childs in l:
    d[vert].append(childs)


d_2=defaultdict(int)
for i in range(1,N+1):
    d_2[i]=0

for p,x in p:
    d_2[p]+=x

for n in d_2.keys():
    for m in d[n]:
        d_2[m]+=d_2[n]

ans=d_2.values()
print(*ans)
### BUGGY CODE ###

# 169 B
N = int(input())
A = list(map(int, input().split()))
ans = A[0]
for i in range(1, N):
    ans *= A[i]
print(ans) if ans <= 10**18 else print(-1)

### FIXED CODE ###

# 169 B
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 1
for i in range(N):
    ans *= A[i]
    if ans > 10**18:
        print(-1)
        break
else:
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np

N=int(input().rstrip('\n'))
A=np.array([int(x) for x in input().rstrip('\n').split()])
res = 0
for i in range(N):
  if i+1 in A:
    a = np.where(A==i+1)
    b = a[0][0]
    A = A[b:]
    res += 1
  else:
    break
if res == 0:
  print(-1)
else:
  print(N-res)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input().rstrip('\n'))
A=[int(x) for x in input().rstrip('\n').split()]
now = 0
for x in range(N):
  if A[x] == now+1:
    now += 1
if now == 0:
  print(-1)
else:
  print(N-now)
### BUGGY CODE ###

import bisect

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

A,B,C = sorted(A),sorted(B),sorted(C)

a_max = N
c_min = 0
ans = 0


for j in range(N):
    b = B[j]

    a_max = bisect.bisect_left(A,b,0,N)
    c_min = bisect.bisect_right(C,b,0,N)



    ans += len(A[:a_max]) * len(C[c_min:])

print(ans)


### FIXED CODE ###

import bisect

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

A,B,C = sorted(A),sorted(B),sorted(C)

a_max = 0
c_min = 0
ans = 0

for j in range(N):
    b = B[j]

    a_max = bisect.bisect_left(A,b,a_max,N)
    c_min = bisect.bisect_right(C,b,c_min,N)
    ans += (a_max) * (N-c_min)

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

n = int(input())

# c = N - a*b
cnt = 0
for a in range(1, n, 1):
    for b in range(1, n, 1):
        if n <= a*b:
            break
        else:
            cnt += 1

print(cnt)

### FIXED CODE ###

n = int(input())

# c = N - a*b
cnt = 0
for a in range(1, n, 1):
    for b in range(1, n, 1):
        if n <= a*b:
            break
        else:
            if a != b:
                cnt += 2
            else:
                cnt += 1
                break

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

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

w = [-1 for i in range(N)]
v = [-1 for i in range(N)]

for i in range(N):
    w[i],v[i] = map(int,input().split())
    

def dfs(i,j):
    #終了条件
    if i == N:
        res = 0
    #残りの容量が足りない場合は次の荷物へ
    elif  j<w[i]:
        res = dfs(i+1,j)
    else:
        #選択しない場合/する場合
        res = max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i])
    return res

print(dfs(0,W))


### FIXED CODE ###

from itertools import accumulate

def chk(samp):
    for i in samp:
        print(samp)

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

w = [0 for i in range(N)]
v = [0 for i in range(N)]

for i in range(N):
    w[i],v[i]=map(int,input().split())



#価値毎に置き換える
wl = [[] for i in range(4)]

#価値ごとのりすとに入れていく
for i in range(N):
    wl[w[i]-w[0]].append(v[i])


#ソートして最初に0を追加する。0は選択しない場合
for i in range(4):
    wl[i].sort(reverse = 1)
    wl[i].insert(0,0)
    

#累積和を作る
for i in range(4):
    wl[i] = list(accumulate(wl[i]))
    
#出力用変数
out = 0


for i,wl0 in enumerate(wl[0]):
   for j,wl1 in enumerate(wl[1]):
       for k,wl2 in enumerate(wl[2]):
           for l,wl3 in enumerate(wl[3]):
               if i*(w[0])+j*(w[0]+1)+k*(w[0]+2)+l*(w[0]+3) > W:
                   pass
               else:
                   out = max(out,wl0+wl1+wl2+wl3)
                   
print(out)
### BUGGY CODE ###

import math
from functools import reduce


def gcd(a, b, c):
    ans = math.gcd(a, b)
    ans = math.gcd(ans, c)

    # abc = [a, b, c]
    # for _ in [[0, 1], [0, 2], [1, 2]]:
    #     a0 = max(abc[_[0]], abc[_[1]])
    #     a1 = min(abc[_[0]], abc[_[1]])

    #     i = 0
    #     while True:
    #         tmp = a0 % a1
    #         if tmp == 0:
    #             gcds.append(a1)
    #             break
    #         a0 = a1
    #         a1 = tmp

    return ans

# def gcd(*numbers):
#     return reduce(math.gcd, numbers)


k = int(input())

s = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            s += gcd(a, b, c)

print(s)


### FIXED CODE ###

import math
# from functools import reduce
import itertools


def gcd(a, b, c):
    ans = math.gcd(a, b)
    ans = math.gcd(ans, c)

    return ans

# def gcd(*numbers):
#     return reduce(math.gcd, numbers)

k = int(input())

elem = [i+1 for i in range(k)]

combs = itertools.combinations_with_replacement(elem, 3)

tmp = [1, 2, 3]

s = 0
for comb in combs:
    s += sum(tmp[:len(set(comb))]) * gcd(comb[0], comb[1], comb[2])
# for a in range(1, k+1):
#     for b in range(1, k+1):
#         for c in range(1, k+1):
#             s += gcd(a, b, c)

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

N,K,Q = map(int,input().split())
lsN = [K]*N
for i in range(Q) :
    lsN = list(map(lambda x: x-1, lsN))
    p = int(input())
    lsN[p-1] = lsN[p-1]+1

for i in lsN:
    if i > 0:
        print('Yes')
    elif i <= 0:
        print('No')

### FIXED CODE ###

N,K,Q = map(int,input().split())
lsN = [K-Q]*N
for i in range(Q) :
    p = int(input())
    lsN[p-1] = lsN[p-1]+1

for i in lsN:
    if i > 0:
        print('Yes')
    elif i <= 0:
        print('No')
### BUGGY CODE ###

INF = 10**18

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

lt = [-INF for _ in range(K + 1)]
rt = [-INF for _ in range(K + 1)]

j = -1
for i in range(1, K + 1):
    while True:
        j += 1
        if S[j] == 'o' and j - lt[i - 1] > C:
            lt[i] = j
            break

j = -1
for i in range(1, K + 1):
    while True:
        j += 1
        if S[::-1][j] == 'o' and j - rt[i - 1] > C:
            rt[i] = j
            break

lt = lt[1:]
rt = [N - x - 1 for x in rt[1:]][::-1]

for i in range(K):
    if lt[i] == rt[i]:
        print(lt[i] + 1)

### FIXED CODE ###

INF = 10**18

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

lt = [-INF for _ in range(K + 1)]
rt = [-INF for _ in range(K + 1)]

j = -1
for i in range(1, K + 1):
    while True:
        j += 1
        if S[j] == 'o' and j - lt[i - 1] > C:
            lt[i] = j
            break

j = -1
for i in range(1, K + 1):
    while True:
        j += 1
        if S[-1 - j] == 'o' and j - rt[i - 1] > C:
            rt[i] = j
            break

lt = lt[1:]
rt = rt[1:]
rt = [N - x - 1 for x in rt]
rt = rt[::-1]

res = []

for i in range(K):
    if lt[i] == rt[i]:
        res.append(lt[i] + 1)

print('\n'.join(map(str, res)))
### BUGGY CODE ###

def calc_factorial(n):
    if n == 0:
        return 1
    else:
        num = 1
        for i in range(2, n+1):
            num = num * i
        return num


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

count = 0
num_A = 0
max_A = int(K / A)
fact_N = calc_factorial(N)

for num_A in range(N):
    left_beauty = K - num_A * A
    # print("left_b: {}".format(left_beauty))

    if left_beauty % B == 0:
        # print("OK")
        num_B = int(left_beauty / B)

        comb_A = int(fact_N/(calc_factorial(num_A)*calc_factorial(N-num_A)))
        comb_B = int(fact_N/(calc_factorial(num_B) * calc_factorial(N - num_B)))

        count += comb_A * comb_B

        # print("comb_A: {}, comb_B: {}, count: {}".format(comb_A, comb_B, count))

print(count % 998244353)


### FIXED CODE ###

N, A, B, K = map(int, input().split(" "))
mod = 998244353
ncr = [1] * (N + 1)
v = 1

for i in range(N):
    v = (v * ((N - i) % mod) * pow((i + 1), mod - 2, mod)) % mod
    ncr[i + 1] = v % mod

pat = 0
for a in range(N + 1):
    if (K - (a * A) < 0):
        break
    if (K - (a * A)) % B == 0 and ((K - (a * A)) // B) <= N:
        pat += ncr[a] * ncr[(K - (a * A)) // B]
        pat %= mod

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

N, K = map(int,input().split( ))
H =[]
for i in range(N):
	h = int(input())
	H.append(h)
ansl = []
H.sort()
for i in range(N - K + 1):
	HK = H[i:i+K]
	ans = max(HK)-min(HK)
	ansl.append(ans)
print(min(ansl))


### FIXED CODE ###

N, K = map(int,input().split( ))
H =[]
for i in range(N):
	h = int(input())
	H.append(h)
ansl = []
H.sort()

for i in range(N - K + 1):
	#HK = H[i:i+K]
	#ans = max(HK)-min(HK)
	ans = H[i + K - 1] - H[i]
	ansl.append(ans)

print(min(ansl))
### BUGGY CODE ###

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

cnt = 0
for i in range(N):
  for j in range(A[i]+i,N):
    if j-i==A[i]+A[j]:
      cnt += 1
print(cnt)

### FIXED CODE ###

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

B = [0 for _ in range(N)]
C = [0 for _ in range(N)]
for i in range(N):
  B[i] = i - A[i]
  C[i] = i + A[i]
lis1 = collections.Counter(B)
lis2 = collections.Counter(C)
count = 0
for key, value in lis1.items():
  if key in lis2:
    count += value * lis2[key]
print(count)
### BUGGY CODE ###

n = int(input())
ans = 1
for a in list(map(int, input().split())):
  ans = ans * a
print("-1" if ans > 10**18 else ans)

### FIXED CODE ###

n = int(input())
aa = list(map(int, input().split()))
if 0 in aa:
  print(0)
else:
  ans = 1
  for a in aa:
    ans = ans * a
    if ans > 10**18:
      break
  print(-1 if ans > 10**18 else ans)
### BUGGY CODE ###

a,b,m=map(int, input().split())
rei=list(map(int, input().split())) 
den=list(map(int, input().split())) 
cou = [0] * m
ans = 100000
for i in range(m):
	cou[i]=list(map(int, input().split()))
	c=rei[cou[i][0]-1]+den[cou[i][1]-1]-cou[i][2]
	if ans>c:
		ans=c
for i in range(b):
	for j in range(a):
		c=rei[j]+den[i]
		
		if ans>c:
			ans=c
print(ans)

### FIXED CODE ###

m=list(map(int, input().split()))
rei=list(map(int, input().split())) 
den=list(map(int, input().split())) 
cou = [0] * m[2]
ans = []
for i in range(m[2]):
	cou[i]=list(map(int, input().split()))
	ans.append(rei[cou[i][0]-1]+den[cou[i][1]-1]-cou[i][2])

ans.append(min(rei)+min(den))
print(min(ans))
### BUGGY CODE ###

import sys
N,K,Q =map(int,input().split())
F = {}
A = []
for l in sys.stdin:
    A.append(int(l))
for i in range(N):
    cnt = A.count(i+1)
    Point = F[str('A'+ str(i+1))] = K - (Q - cnt)
    if Point >= 1 :
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N,K,Q=map(int,input().split())
L=[K]*N
for i in range(Q):
    A=int(input())
    L[A-1] += 1

for i in L:
    if i - Q > 0 :
        print("Yes")
    else :
        print("No")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = sorted([a[i] - i - 1 for i in range(n)])
c = [i + (0 - b[0]) for i in b]

d = c[0]
ans = []
count = 0
while c[-1] != 0:
    ans.append(sum([abs(i) for i in c]))
    for e, name in enumerate(c):
       if name >0:
           break
    c = [i - name for i in c]
    if count >0:
        if ans[-1] >= ans[-2]:
            break
    count += 1

ans.append(sum([abs(i) for i in c]))
print(min(ans))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = sorted([a[i] - i - 1 for i in range(n)])
c = [i + (0 - b[0]) for i in b]

d = []
if n == 1:
    print(0)
else:
    if n % 2 == 1:
        d.append(0 - c[n//2])
    else:
        d.append(0 - c[n//2])
        d.append(0 - c[n//2 - 1])
        d.append(1 - c[n//2])
        d.append(-1 - c[n//2 - 1])

    ans = []
    for j in d:
        e = [i + j for i in c]
        ans.append(sum([abs(i) for i in e]))

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

n = int(input())
l = [i for i in range(1,n+1)]
print(sum(l)-l[-1])

### FIXED CODE ###

n = int(input())

ans = n * (n-1) // 2

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

import bisect

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

place = [-1] * (N + 1)
for i in range(N):
    p = P[i]
    place[p] = i

ans = 0
big_place = [place[N]]
for i in range(N - 1, 0, -1):
    pos = bisect.bisect_left(big_place, place[i])
    if pos < len(big_place):
        right = big_place[pos]
    else:
        right = N
    if pos + 1 < len(big_place):
        right2 = big_place[pos + 1]
    else:
        right2 = N
    if pos - 1 >= 0:
        left = big_place[pos - 1]
    else:
        left = -1
    if pos - 2 >= 0:
        left2 = big_place[pos - 2]
    else:
        left2 = -1

    if left >= 0:
        left_cand = left - left2
    else:
        left_cand = 0
    right_cand = right - place[i]

    ans += i * left_cand * right_cand

    if right < N:
        right_cand = right2 - right
    else:
        right_cand = 0
    left_cand = place[i] - left
    ans += i * left_cand * right_cand

    big_place1 = big_place[:pos]
    big_place2 = big_place[pos:]
    big_place = big_place1 + [place[i]] + big_place2

print(ans)


### FIXED CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    # i+1番目からR番目まで足すとt以上となるような最小のRを返す
    def bisect_plus(self, i, t):
        L = i
        R = self.size
        R_prev = R
        sum_i = self.sum(i)
        while True:
            range_sum = self.sum(R) - sum_i
            if range_sum < t:
                if R == self.size:
                    return self.size + 1
                L, R = R, R_prev
            else:
                R_prev = R
                R = (L + R + 1) // 2
                if R == R_prev:
                    return R

    # L番目からi-1番目まで足すとt以上となるような最小のRを返す
    def bisect_minus(self, i, t):
        L = 1
        R = i
        L_prev = L
        sum_i = self.sum(i - 1)
        while True:
            range_sum = sum_i - self.sum(L - 1)
            if range_sum < t:
                if L == 1:
                    return 0
                L, R = L_prev, L
            else:
                L_prev = L
                L = (L + R) // 2
                if L == L_prev:
                    return L


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

place = [-1] * (N + 1)
for i in range(N):
    p = P[i]
    place[p] = i

ans = 0
big_place = Bit(N)
big_place.add(place[N] + 1, 1)
for i in range(N - 1, 0, -1):
    pos = place[i] + 1
    right = big_place.bisect_plus(pos, 1)
    right2 = big_place.bisect_plus(pos, 2)
    left = big_place.bisect_minus(pos, 1)
    left2 = big_place.bisect_minus(pos, 2)
    if left > 0:
        left_cand = left - left2
    else:
        left_cand = 0
    right_cand = right - pos
    ans += i * left_cand * right_cand

    if right < N + 1:
        right_cand = right2 - right
    else:
        right_cand = 0
    left_cand = pos - left
    ans += i * left_cand * right_cand

    big_place.add(pos, 1)

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

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

ans = 1
limit = 10**18
for i in range(n):
    ans *= a[i]

print(-1 if ans > limit else ans)


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    if 0 in A:
        print(0)
        return
    prod = 1
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return
    print(prod)


main()