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

import sys
input = sys.stdin.readline
from collections import deque

def bfs(u):
    dist = [-1 for _ in range(n)]
    dist[u] = 0
    que = deque([])
    que.append(u)
    
    while que:
        v = que.popleft()
        for nv in G[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = dist[v] + 1
            que.append(nv)

    for d in dist:
        if d == 0:
            continue
        ans[d-1] += 1
    return ans


n, x, y = map(int,input().split())
G = [[] for _ in range(n)]
for i in range(n-1):
    G[i].append(i+1)
    G[i+1].append(i)
G[x-1].append(y-1)
G[y-1].append(x-1)

ans = [0]*(n-1)
for i in range(n):
    bfs(i)

for i in ans:
    print(i//2)

### FIXED CODE ###

n, x, y = map(int,input().split())
cnt = [0 for _ in range(n)]
for i in range(1, n):
    for j in range(i+1, n+1):
        if i <= x and j >= y:
            cnt[(x-i)+1+(j-y)] += 1
        else:
            c = min(j-i, abs(x-i)+1+abs(y-j))
            cnt[c] += 1
for i in cnt[1:]:
    print(i)
### BUGGY CODE ###

import math
n,m,k = map(int,input().split())
ss = (math.factorial(m*n)//math.factorial(k))//math.factorial(m*n-k)
s = (ss*k*(k-1))//2
r = 10**9 +7
xav = 0
yav = 0
for i in range(1,m):
  xav += (i*(m-i)*n**2)%r
for j in range(1,n):
  yav += (j*(n-j)*m**2)%r
av = xav + yav
d = (m*n*(m*n-1))//2
print(int(((av*s)//d)%r))



### FIXED CODE ###

n,m,k = map(int,input().split())
x = m*n
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
ss = cmb(x,k)
s = (ss*k*(k-1))//2
r = 10**9 +7
av = (((m**3-m) *n**2)//6 + ((n**3-n)*m**2)//6)%r
d = (x*(x-1))//2
print(int(((av*s)//d)%r))
### BUGGY CODE ###

import sys
from operator import itemgetter
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
def main():
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while(e[0] > d):
			if cont == True:
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			else:
				mini = min(kouho)
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			cont = True
			if q < Q-1:
				q = q + 1
				d = int(inputs())
			else:
				flag = True
				q = q + 1
				break
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			cont = False
	for t in [None]*(Q-q):
		print(-1)
		
def sub():
	V = [list(map(int,inputs().split())) for p in [0]*N]
	M = [int(inputs()) for p in [0]*Q]
	V.sort(key = lambda x:(x[2],x[0],x[1]))
	for v in V:
		v[0] -= v[2]
		v[1] -= v[2] + 1
	for m in M:
		for n in range(N):
			if V[n][0] <=m and m <= V[n][1]:
				print(V[n][2])
				break
		else:
			print(-1)


if N>100000:
	sub()
else:
	main()

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()
### BUGGY CODE ###

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

dev = 1000000007

all_s = 2**len(iwa)-1

bad = []
for i in range(len(iwa)):
  for j in range(i+1, len(iwa)):
    if iwa[i][0]*iwa[j][0]+iwa[i][1]*iwa[j][1] == 0:
      bad.append(2**i+2**j)
bad_s = 0
for i in range(1, all_s+1):
  for j in bad:
    # print(bin(i), bin(j), bin(i&j))
    if bin(i&j)==bin(j):
      bad_s+=1
      break
print((all_s-bad_s)%dev)

### FIXED CODE ###

from math import gcd
 
n=int(input())
mod = 10**9+7
 
d = dict()
zeros=0
for _ in range(n):
  a,b=map(int,input().split())
  if not any((a,b)):
    zeros+=1
    continue
  if all((a,b)):
    g = gcd(a,b)*(a//abs(a))
  elif a:
    g = a
  else:
    g = b
  
  p = a//g,b//g
  d[p] = d.get(p,0)+1
 
ans = 1
done = set()
for (a,b),v in d.items():
  if (-b,a) in done or (b,-a) in done:
    continue
  done.add((a,b))
  w=d.get((-b,a),0)+d.get((b,-a),0)
  ans *= (pow(2,v,mod)+pow(2,w,mod)-1)
  ans %= mod
print((ans+zeros-1+mod)%mod)
### BUGGY CODE ###

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

import io
import sys
import math

def solve(s,l,r):
    # implement process
    str = s[l-1:r]
    return str.count("AC")

def main():
    # input
    n,q = map(int, input().split())
    s = input()
    
    # process
    ans = ""
    for _ in range(q):
        l,r = map(int, input().split())
        print(str( solve(s,l,r) ))
         
### DEBUG I/O ###
_DEB = 0   # 1:ON / 0:OFF

_INPUT = """\
8 3
ACACTACG
3 7
2 3
1 8
"""
_EXPECTED = """\
2
0
3

"""

def logd(str):
    """usage:
    if _DEB: logd(f"{str}")
    """
    if _DEB: print(f"[deb] {str}")

### MAIN ###
if __name__ == "__main__":
    if _DEB:
        sys.stdin = io.StringIO(_INPUT)
        print("!! Debug Mode !!")

    main()



### FIXED CODE ###

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

import io
import sys
import math

def solve(ac_lst,l,r):
    # implement process
    #l=2,r=3
    if l == 1:
        return ac_lst[r-2]
    return ac_lst[r-2] - ac_lst[l-2]
    

def make_ac_lst(s):
    ac_lst = [0] * len(s)
    for i in range(len(s)-1):
        if i != 0:
            ac_lst[i] += ac_lst[i-1]
        if s[i] == "A" and s[i+1] == "C":
            ac_lst[i] += 1
    ac_lst[-1] = ac_lst[-2]

    if _DEB: logd(f"{ac_lst}")
    return ac_lst

def main():
    # input
    n,q = map(int, input().split())
    s = input()
    
    # process
    ans = ""
    ac_lst = make_ac_lst(s)

    for _ in range(q):
        l,r = map(int, input().split())
        ans += str( solve(ac_lst,l,r) ) + "\n"
         
    # output    
    print(ans)
    return ans
        
### DEBUG I/O ###
_DEB = 0   # 1:ON / 0:OFF

_INPUT = """\
8 3
ACACTAAC
7 8
2 3
1 8
"""
_EXPECTED = """\
2
0
3

"""

def logd(str):
    """usage:
    if _DEB: logd(f"{str}")
    """
    if _DEB: print(f"[deb] {str}")

### MAIN ###
if __name__ == "__main__":
    if _DEB:
        sys.stdin = io.StringIO(_INPUT)
        print("!! Debug Mode !!")

    ans = main()

    if _DEB:
        print()
        if _EXPECTED.strip() == ans.strip(): print("!! Success !!")
        else: print(f"!! Failed... !!\nANSWER:   {ans}\nExpected: {_EXPECTED}")
### BUGGY CODE ###

n = int(input())
h = input().split()
h_lis = []
for i in range(n):
    h_lis.append(int(h[i]))
cnt_max = 0
for i in range(n):
    tmp_cnt = -1
    last = float('inf')
    for j in range(i, n):
#         print(h_lis[i], h_lis[j])
        if h_lis[j] <= last:
            tmp_cnt += 1
            last = h_lis[j]
        else:
            cnt_max = max(cnt_max, tmp_cnt)
            break
        cnt_max = max(cnt_max, tmp_cnt)
print(cnt_max)

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
last = 0
cnt_lis = []
for i in range(n):
    if h[i] <= last:
        cnt_lis.append(cnt_lis[i - 1] + 1)
    else:
        cnt_lis.append(0)
    last = h[i]
print(max(cnt_lis))
### BUGGY CODE ###

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7

dp = [0] * (1 << n)
dp[0] = 1

for bit in range((1 << n) - 1):
    i = bin(bit).count('1')
    for j in range(n):
        newbit = bit | (1 << j)
        if ((bit >> j) & 1 == 0) and (a[i][j] == 1):
            dp[newbit] += dp[bit]
            dp[newbit] %= mod
print(dp[-1])


### FIXED CODE ###

mod = 10**9+7
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
dp = [0]*(1 << n)
dp[0] = 1
for i in range(1, 1 << n):
    k = bin(i).count("1")
    for j in range(n):
        if i >> j & 1 and a[k-1][j]:
            dp[i] += dp[i ^ (1 << j)]
    dp[i] %= mod
print(dp[(1 << n)-1])
### BUGGY CODE ###

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

max_val = 0
for ind in range(n-k+1):
  if sum(p[ind:ind+k]) >= max_val:
    max_val = sum(p[ind:ind+k])
max_val = float(max_val)
k = float(k)
print(max_val/2+k/2)

### FIXED CODE ###

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

exps = [(elm+1)/2 for elm in p]
#print(exps)
cum_sums = [0]*(n+1)
for ind in range(n):
  cum_sums[ind+1] = cum_sums[ind]+exps[ind]
#print(cum_sums)
k_exps = [cum_sums[ind+k]-cum_sums[ind] for ind in range(n-k+1)]
#print(k_exps)
print(max(k_exps))
### BUGGY CODE ###

import itertools
n,k=map(int,input().split())
X,Y,XY=[],[],[]
for i in range(n):
  x,y=map(int,input().split())
  X.append(x)
  Y.append(y)
  XY.append([x,y])
def count(x1,x2,y1,y2):
  ct=0
  if x1>x2:
    x1,x2=x2,x1
  if y1>y2:
    y1,y2=y2,y1
  for x,y in XY:
    if x1<=x<=x2 and y1<=y<=y2:
      ct+=1
  return ct
ans=float("inf")
for x1,x2 in itertools.combinations(X,2):
  for y1,y2 in itertools.combinations(Y,2):
    if count(x1,x2,y1,y2)==k:
      ans=min(ans,abs((x1-x2)*(y1-y2)))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import itertools
n,k=map(int,input().split())
X,Y,XY=[0]*n,[0]*n,[0]*n
for i in range(n):
  x,y=map(int,input().split())
  X[i],Y[i],XY[i]=x,y,[x,y]
X.sort()
Y.sort()
def count(x1,x2,y1,y2):
  ct=0
  for x,y in XY:
    if x1<=x<=x2 and y1<=y<=y2:
      ct+=1
  return ct
ans=float("inf")
for x1,x2 in itertools.combinations(X,2):
  for y1,y2 in itertools.combinations(Y,2):
    if count(x1,x2,y1,y2)==k:
      ans=min(ans,abs((x1-x2)*(y1-y2)))
print(ans)
### BUGGY CODE ###

from itertools import accumulate
N, M, K = map(int, input().split())
A = [0] + list(accumulate([int(i) for i in input().split()]))
B = [0] + list(accumulate([int(i) for i in input().split()]))
ans = 0
for n in range(N+1):
    for m in reversed(range(M+1)):
        if A[n] + B[m] <= K:
            ans = max(ans, n+m)
            break
print(ans)

### FIXED CODE ###

import itertools
N,M,K = map(int,input().split())
A = [0]+list(map(int,input().split()))
B = [0]+list(map(int,input().split()))
SA = list(itertools.accumulate(A))
SB = list(itertools.accumulate(B))
ans = 0
j = len(B)-1
for i in range(len(SA)):
    while(j>=0):
        if SA[i] + SB[j] <= K:
            ans = max(ans,i+j)
            break
        j-=1
print (ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
S = input().strip()
Q = int(input())
K = list(map(int,input().split()))

for k in K:
    ans = 0
    m = defaultdict(int)
    for i,s in enumerate(S):
        if i >= k:
            pre = S[i-k]
            if pre == 'D':
                m['D'] -= 1
                m['DM'] -= m['M']
            elif pre == 'M':
                m['M'] -= 1
        if s == 'D':
            m['D'] += 1
        if s == 'M': 
            m['DM'] += m['D']
            m['M'] += 1
        if s == 'C':
            ans += m['DM']
        #print(s,m)
    print(ans)



### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
S = input().strip()
Q = int(input())
K = list(map(int,input().split()))

'''
import random
import string
S = "".join(random.choices(string.ascii_uppercase, k=10**6))
Q =75 
K = [random.randint(1,10**6) for i in range(Q)]
'''

for k in K:
    ans = 0
    m = [0] * 3
    for i,s in enumerate(S):
        if i >= k:
            pre = S[i-k]
            if pre == 'D':
                m[0] -= 1 # m['D'] -= 1
                m[2] -= m[1] # m['DM'] -= m['M']
            elif pre == 'M':
                m[1] -= 1 # m['M'] -= 1
        if s == 'D':
            m[0] += 1 # m['D'] += 1
        if s == 'M': 
            m[2] += m[0] # m['DM'] += m['D']
            m[1] += 1# m['M'] += 1
        if s == 'C':
            ans += m[2] # ans += m['DM']
        #print(s,m)
    print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
array = []
for _ in range(N):
    a, b = map(int, input().split())
    array.extend([a] * b)
array.sort()
print(array[K - 1])


### FIXED CODE ###

from collections import Counter
N, K = map(int, input().split())
c = Counter()
for _ in range(N):
    a, b = map(int, input().split())
    c[a] += b
for item in sorted(c.items(), key=lambda x: x[0]):
    if item[1] >= K:
        print(item[0])
        break
    else:
        K -= item[1]
### BUGGY CODE ###

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

### FIXED CODE ###

N=int(input())
S=input()
ans = 0
for i in range(0,N):
  for j in range(i+1,N):
    if S[i] != S[j]:
      k = j+j-i
      if k < N:
        if S[i] != S[k] and S[j] != S[k]:
          #print(i,j,k)
          ans += 1
ans = (S.count('R') * S.count('G') * S.count('B')) - ans
print(ans)
### BUGGY CODE ###

from sys import stdin, stdout
s = input()
n = len(s)
d = dict()

if len(s) <= 3:
    print(0)
    exit()


suffix_rems = [-1]*n
suffix_rems[-1] = int(s[-1])
suffix_rems[-2] = int(s[-2:])
suffix_rems[-3] = int(s[-3:])

rems_d = dict()
# rems_d[0] = [n]
# rems_d[int(s[-1])] = [n-1]
# rems_d[int(s[-2:])] = [n-2]
# rems_d[int(s[-3:])] = [n-3]
rems_d[0] = 1
rems_d[int(s[-1])] = 1
rems_d[int(s[-2:])] = 1
rems_d[int(s[-3:])] = 1


special_keys = set()
for i in range(n-3)[::-1]:
    rem = (10**(n-i-1) * int(s[i]) + suffix_rems[i + 1])%2019

    if rem in rems_d:
        rems_d[rem] += 1
        special_keys.add(rem)

    else:
        rems_d[rem] = 1

    suffix_rems[i] = rem

ans = 0
for key in special_keys:
    t = rems_d[key]
    ans += (t*(t-1))//2


print(ans)

### FIXED CODE ###

from sys import stdin, stdout
s = input()
n = len(s)


if len(s) <= 3:
    print(0)
    exit()

suffix_rems = [-1]*n
suffix_rems[-1] = int(s[-1])
suffix_rems[-2] = int(s[-2:])
suffix_rems[-3] = int(s[-3:])

rems_d = dict()
rems_d[0] = 1
rems_d[int(s[-1])] = 1
rems_d[int(s[-2:])] = 1
rems_d[int(s[-3:])] = 1

special_keys = set()
for i in range(n-3)[::-1]:
    rem = (pow(10, n-i-1, 2019) * int(s[i]) + suffix_rems[i + 1])%2019

    if rem in rems_d:
        rems_d[rem] += 1
        special_keys.add(rem)
    else:
        rems_d[rem] = 1

    suffix_rems[i] = rem

ans = 0
for key in special_keys:
    t = rems_d[key]
    ans += (t*(t-1))//2

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

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

A_list = list(itertools.permutations(A, N))
ans = 10**8
for i in A_list:
    tmp = 0
    
    if i[0] == min(A) and i[2] == max(A):
        pass
    else:
        for j in range(N-1):
            if abs((i[j+1]) - (i[j])) <= abs(K-i[j+1]):
                tmp = tmp +  abs((i[j+1]) - (i[j]))
            else:
                tmp = tmp + abs(K-i[j+1])
        
        if tmp <= ans:
            ans = tmp
print(ans)


### FIXED CODE ###

K,N = map(int, input().split())
A = [int(a) for a in input().split()]

ans = A[-1]-A[0]
for i in range(N-1):
    ans = min(ans, K-A[i+1]+A[i])
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from bisect import bisect_right


def solve(N: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    ans  = 0
    A.sort()
    B.sort()
    C.sort()
    for i in range(N):
        bi = bisect_right(B, A[i])
        for j in range(bi, N):
            ci = bisect_right(C, B[j])
            ans += N-ci

    print(ans)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    C = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B, C)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from bisect import bisect_right, bisect_left


def solve(N: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    ans  = 0
    A.sort()
    B.sort()
    C.sort()
    for i in range(N):
        ai = bisect_left(A, B[i])
        ci = bisect_right(C, B[i])
        ans += (ai) * (N-ci)

    print(ans)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    C = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B, C)

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

import sys
input = sys.stdin.readline

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

dp=[[0]*(w+1) for _ in range(n+1)]

for i in range(n):
    for sum_w in range(w+1):
        if sum_w-wv[i][0]>=0:
            dp[i+1][sum_w]=max(dp[i][sum_w], dp[i][sum_w-wv[i][0]]+wv[i][1])
        else:
            dp[i+1][sum_w]=dp[i][sum_w]

print(dp[n][w])


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

dp=[[0]*(w+1) for _ in range(n+1)]

for i in range(n):
    for sum_w in range(w+1):
        if sum_w-wv[i][0]>=0:
            dp[i+1][sum_w]=max(dp[i][sum_w], dp[i][sum_w-wv[i][0]]+wv[i][1])
        else:
            dp[i+1][sum_w]=dp[i][sum_w]

print(dp[n][w])
### BUGGY CODE ###

import math
n=int(input())

def gcd2(a,b,c):
    d=math.gcd(a,b)
    e=math.gcd(c,d)
    return e
    
s=0
for i1 in range(1,n+1):
    for i2 in range(1,n+1):
        for i3 in range(1,n+1):
            s+=gcd2(i1,i2,i3)

print(s)



### FIXED CODE ###

import math
n=int(input())

def gcd2(a,b,c):
    d=math.gcd(a,b)
    e=math.gcd(c,d)
    return e
    
s=0
s1=0
s2=0
s3=0

for i in range(1,n+1):
    s1+=i
    for i2 in range(i+1,n+1):
        s2+=math.gcd(i,i2)
        for i3 in range(i2+1,n+1):
            s3+=gcd2(i,i2,i3)

s=s1+6*s2+6*s3

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

a = [0]*3
a[0],a[1],a[2],n = map(int,input().split())
a.sort()
cnt = 0
for i in range(n//a[2]+1):
    for j in range(n//a[1]+1):
        d = n-a[2]*i-a[1]*j
        if d%a[0] == 0 and d >= 0:
            cnt += 1
print(cnt)


### FIXED CODE ###

a = [0]*3
a[0],a[1],a[2],n = map(int,input().split())
a.sort()
cnt = 0
for i in range(n//a[2]+1):
    for j in range((n-i*a[2])//a[1]+1):
        d = n-a[2]*i-a[1]*j
        if d%a[0] == 0 and d >= 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

import numpy as np

n = int(input())
a = [int(input()) for _ in range(n)]
sort_a = list(np.sort(a))
sort_arg = np.argsort(a)
for i in range(n):
    tmp_l = sort_a[:]
    tmp_l.pop(sort_arg[i])
    print(tmp_l.pop(-1))

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
sort_a = sorted(a)
max_a = max(a)
max_ind = 0
for i in range(n):
    if a[i] == max_a: max_ind = i
for i in range(n):
    ans = max_a if i != max_ind else sort_a[-2]
    print(ans)
### BUGGY CODE ###

import sys
from heapq import heappop, heappush
from collections import defaultdict

INF = 10**20
N,M = map(int,input().split(' '))
g = defaultdict(list)
for i in range(2,N+1):
    g[i].append((i-1,0))
for i in range(1,M+1):
    input = sys.stdin.readline
    l,r,c = list(map(int,input().split(' ')))
    g[l].append((r,c))

d = [INF] * (N+1)
d[1] = 0
que = []
heappush(que,(1,0))
while que:
    s, dist = heappop(que)
    if d[s] < dist:
        continue
    for t,c in g[s]:
        if d[t] > d[s] + c:
            d[t] = d[s] + c
            heappush(que,(t,d[t]))
if d[N] == INF:
    print(-1)
    exit()
print(d[N])
        



### FIXED CODE ###

import sys
from heapq import heappop, heappush
from collections import defaultdict
input = sys.stdin.buffer.readline

INF = 10**20
N,M = map(int,input().split())
g = defaultdict(list)
for i in range(2,N+1):
    g[i].append((i-1,0))
for i in range(1,M+1):
    l,r,c = list(map(int,input().split()))
    g[l].append((r,c))

d = [INF] * (N+1)
d[1] = 0
que = []
heappush(que,(1,0))
while que:
    s, dist = heappop(que)
    if d[s] < dist:
        continue
    for t,c in g[s]:
        if d[t] > d[s] + c:
            d[t] = d[s] + c
            heappush(que,(t,d[t]))
if d[N] == INF:
    print(-1)
    exit()
print(d[N])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""

def simulation(N, K, A_list):
    for k in range(min(K, 100)):
        next_A_list = [0 for i in range(N)]
        for i in range(N):
            d = A_list[i]
            for j in range(i-d, i+d+1):
                if j >= 0 and j <= N-1:
                    next_A_list[j] += 1
        A_list = next_A_list[:]
        #print(" ".join([ str(i).zfill(2) for i in A_list]))
    return A_list

def main():
    N, K = map(int, input().split())
    A_list = list(map(int, input().split()))
    print(" ".join([ str(i) for i in simulation(N, K, A_list)]))

if __name__ == "__main__":
    main()



### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""

def simulation(N, K, A_list):
    for k in range(min(K, 42)):
        #next_A_list = [0 for i in range(N)]
        imos_list = [0 for i in range(N)]
        for i in range(N):
            d = A_list[i]
            imos_list[max(i-d, 0)] += 1
            if i+d+1 <= N-1:
                imos_list[i+d+1] -= 1
            #for j in range(i-d, i+d+1):
            #    if j >= 0 and j <= N-1:
            #        next_A_list[j] += 1
        for i in range(1, N):
            imos_list[i] += imos_list[i-1]
        A_list = imos_list[:]
        #print(" ".join([ str(i).zfill(2) for i in A_list]))
    return A_list

def main():
    N, K = map(int, input().split())
    A_list = list(map(int, input().split()))
    print(" ".join([ str(i) for i in simulation(N, K, A_list)]))

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

n=int(input())
A=list(map(int,input().split()))
MOD = 1000000007
import itertools
c = itertools.combinations(A, 2)
q=0
for v in c:
    q +=v[0]%MOD*v[1]%MOD
print(q%MOD)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
MOD = 1000000007
B=0
tem = sum(A)
for i in range(len(A)):
    tem -= A[i]
    B+= (A[i]%MOD)*(tem%MOD)
print(B%MOD)
### BUGGY CODE ###

n = int(input())
pre = 1
a=list(map(int,input().split()))
for i in range(n):
    pre = pre * a[i]
if pre <= 1000000000000000000:
    print(pre)
else:
    print(-1)


### FIXED CODE ###

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

    if 0 in A:
        print('0')
        return
    prod=1
    for a in A:
        prod*=a
        if prod> 1000000000000000000:
            print('-1')
            return
    print(prod)

ans=main()