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

from collections import deque

h,w = map(int,input().split())
maze = []

for _ in range(h):
    maze.append(input())

ans = 0

move = [[1,0],[-1,0],[0,1],[0,-1]]

for i in range(h):
    for j in range(w):
        if(maze[i][j]=="."):
            dist = [ [99999999]*w for _ in range(h) ]
            
            dq = deque()
            y=i
            x=j
            d=0
            
            dq.append((y,x,d))
            
            while(len(dq)):
                
                y,x,d = dq.popleft()
                dist[y][x]=d
                for m in move:
                    if((0<=x+m[0]<w) and (0<=y+m[1]<h) and
                        (dist[y+m[1]][x+m[0]] > d+1) and
                            (maze[y+m[1]][x+m[0]] == ".")):
                                dq.append((y+m[1],x+m[0],d+1))
                                
            ans = max(ans,d)
            # print(d,i,j)
print(ans)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
maze = []

for _ in range(h):
    maze.append(input())

ans = 0

move = [[1,0],[-1,0],[0,1],[0,-1]]

for i in range(h):
    for j in range(w):
        if(maze[i][j]=="."):
            dist = [ [99999999]*w for _ in range(h) ]
            
            dq = deque()
            y=i
            x=j
            d=0
            dist[y][x]=0
            dq.append((y,x,d))
            
            while(len(dq)):
                
                y,x,d = dq.popleft()
                
                for m in move:
                    if((0<=x+m[0]<w) and (0<=y+m[1]<h) and
                        (dist[y+m[1]][x+m[0]] > d+1) and
                            (maze[y+m[1]][x+m[0]] == ".")):
                                dist[y+m[1]][x+m[0]]=d+1
                                dq.append((y+m[1],x+m[0],d+1))
                                
            ans = max(ans,d)
            # print(d,i,j)
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]
c = N-1
A.sort()
while c > 0:
    num = A[0]^A[c]
    pre_num = A[c]
    B = [A[0],A[c],num]
    while len(B) < N:
        box = num
        num = num^pre_num
        pre_num = box
        B.append(num)
    B.sort()
    if A == B:
        break
    c -= 1
if c > 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]
c = N-1
A.sort()
num = A[0]^A[c]
pre_num = A[c]
B = [A[0],A[c],num]
while len(B) < N:
    box = num
    num = num^pre_num
    pre_num = box
    B.append(num)
B.sort()
if A == B:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N,K=map(int,input().split())
A=sorted(map(int,input().split()))
F=sorted(map(int,input().split()),reverse=True)

l=-1
r=A[-1]*F[0]
while l+1<r:
  x=(l+r)//2
  cnt=0
  for i in range(N):
    cnt+=max(A[i]-x//F[i],0)
  if cnt<=K:
    r=x
  else:
    l=x
    
print(r)

### FIXED CODE ###

N,K=map(int,input().split())
A=sorted(map(int,input().split()))
F=sorted(map(int,input().split()),reverse=True)

l=-1
r=A[-1]*F[0]
while l+1<r:
  x=(l+r)//2
  cnt=0
  for i in range(N):
    cnt+=max(A[i]-x//F[i],0)
  if cnt<=K:
    r=x
  else:
    l=x
    
print(r)
### BUGGY CODE ###

A, B, N = map(int,input().split())
score = 0
for i in range(N//2,N):
    x = i+1
    val = int(A*x/B) - A * int(x/B)
    #print( int(A*x/B) , A * int(x/B))
    if(val > score):
        score = val
print(score)


### FIXED CODE ###

A, B, N = map(int,input().split())
x = min(N,B-1)
val = int(A*x/B) - A * int(x/B)
print(val)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

c = list(input())
c = c[:len(c)-1]
q = int(input())

num = len(c)

hantei = 0

for i in range(q):
    q_i= list(input())
    #print(q_i)
    if q_i[0] == '1' and hantei ==0:
        hantei = 1
    elif q_i[0] == '1' and hantei == 1:
        hantei = 0
    elif (q_i[2] =='1' and hantei == 0) or (q_i[2] == '2' and hantei == 1):
            c = [q_i[4]] +c
    elif (q_i[2] =='2' and hantei == 0) or (q_i[2] == '1' and hantei ==1):
            c += [q_i[4]]



if hantei == 0:
    ans = ''
    for i in range(len(c)):
        ans += c[i]
else:
    ans = ''
    for i in range(len(c)):
        ans = c[i] + ans


print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

c = input()
c = c[:len(c)-1]
q = int(input())

num = len(c)
c_mae = ''
c_ato = ''

hantei = 1

for i in range(q):
    q_i= list(input())
    #print(q_i)
    if q_i[0] == '1':
        hantei *= -1
    elif (q_i[2] =='1' and hantei == 1) or (q_i[2] == '2' and hantei == -1):
        c_mae = q_i[4] + c_mae
    else:
        c_ato += q_i[4]

print(c_mae+c+c_ato if hantei == 1 else (c_mae+c+c_ato)[::-1])
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()

for i in range(Q):
	count = 0
	l, r = map(int, input().split())
	Sr = S[l-1:r]
	print(Sr.count('AC'))
	

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0]*(N+1)
for i in range(N):
	t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)

for i in range(Q):
	l, r = map(int, input().split())
	print(t[r-1] - t[l-1])
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000)

s=input()
x,y=map(int,input().split())
N=len(s)

memo={}
def dfs(startx,starty,direction,num):
    if (startx,starty,direction,num) in memo.keys():
        return memo[(startx,starty,direction,num)]
    if num==N:
        memo[(startx,starty,direction,num)]=0
        memo[(startx,starty,direction,num)]=(startx==x and starty==y)
        return (startx==x and starty==y)

    if s[num]=='F':
        if direction==0:
            memo[(startx,starty,direction,num)]=0
            memo[(startx,starty,direction,num)]=dfs(startx+1,starty,direction,num+1)
            return memo[(startx,starty,direction,num)]
        if direction==90:
            memo[(startx,starty,direction,num)]=0
            memo[(startx,starty,direction,num)]=dfs(startx,starty+1,direction,num+1)
            return memo[(startx,starty,direction,num)]
        if direction==180:
            memo[(startx,starty,direction,num)]=0
            memo[(startx,starty,direction,num)]=dfs(startx-1,starty,direction,num+1)
            return memo[(startx,starty,direction,num)]
        if direction==270:
            memo[(startx,starty,direction,num)]=0
            memo[(startx,starty,direction,num)]=dfs(startx,starty-1,direction,num+1)
            return memo[(startx,starty,direction,num)]

    if s[num]=='T':
        memo[(startx,starty,direction,num)]=0
        if dfs(startx,starty,(direction+90)%360,num+1):
            memo[(startx,starty,direction,num)]=True
            return True
        if dfs(startx,starty,(direction-90)%360,num+1):
            memo[(startx,starty,direction,num)]=True
            return True

        memo[(startx,starty,direction,num)]=False
        return False

if dfs(0,0,0,0):
    print('Yes')
else:
    print('No')


### FIXED CODE ###

from itertools import groupby


s=input()
x,y=map(int,input().split())
data=[s[i] for i in range(0,len(s))]
data=groupby(data)
LR=[]
UD=[]
point='LR'
flag=0
checkx=2**8000
for key,group in data:
    g=len(list(group))
    if key=='F':
        if flag==0:
            checkx=checkx<<g
            flag=1
        else:
            if point=='LR':
                LR.append(g)
            else:
                UD.append(g)
    else:
        if g%2==1:
            if point=='LR':
                point='UD'
            else:
                point='LR'
        flag=1


for i in range(0,len(LR)):
    checkx=(checkx<<LR[i])|(checkx>>LR[i])

checky=2**8000
for i in range(0,len(UD)):
    checky=(checky<<UD[i])|(checky>>UD[i])


if checkx>>(x+8000) &1==1 and checky>>(y+8000) &1==1:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

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

count=0

SUM=["" for i in range(N)]
SUM[0]=A[0]

for i in range(1,N):
    SUM[i] = SUM[i-1]+A[i]

for i in range(N):
    if SUM[i]==0:
        count=count+1

for i in range(1,N):
    for j in range(i-1):
        if SUM[i]-SUM[j]==0:
            count=count+1


print(count)


### FIXED CODE ###

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

SUM=[0 for i in range(N+1)]
SUM[0]=0
 
for i in range(1,N+1):
    SUM[i]=SUM[i-1]+A[i-1]

    
SUM.sort()



for i in range(1,N+1):
    if SUM[i]==SUM[i-1]:
        count=count+1
    else:
        if count!=0:
            score=score+count*(count+1)//2
        count=0
        
if count!=0:
    score=score+count*(count+1)//2

 
print(score)
### BUGGY CODE ###

def main():
    N, K = map(int,input().split())
    h = list(map(int,input().split()))
    
    dp = [0] * N
    dp[1] = abs(h[0] - h[1])
    
    for i in range(2, N):
        dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(i - K, i) if j >= 0])
    
    print(dp[-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N, K = map(int,input().split())
    h = list(map(int,input().split()))
    
    dp = [0] * N
    dp[1] = abs(h[0] - h[1])
    
    for i in range(2, N):
        dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(0, i - K), i))
    
    print(dp[-1])

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

import sys
input = sys.stdin.readline

R, C, K = map(int, input().split())

I = [[0 for j in range(C)] for i in range(R)]
for _ in range(K):
    r, c, v = map(int, input().split())
    I[r-1][c-1] = v   # 0-indexed

dp = [[[0 for k in range(4)]
       for j in range(C+1)] for i in range(R+1)]
for i in range(R):
    for j in range(C):
        for k in range(2, -1, -1):
            dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j][k]+I[i][j])
        for k in range(4):
            dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][k])
            dp[i][j+1][k] = max(dp[i][j+1][k], dp[i][j][k])


# print(*dp, sep=' \n')

ans = 0
for k in range(4):
    ans = max(ans, dp[R-1][C-1][k])
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

R, C, K = map(int, input().split())

I = [[0]*C for i in range(R)]
for _ in range(K):
    r, c, v = map(int, input().split())
    I[r-1][c-1] = v   # 0-indexed

dp0 = [[0 for j in range(C+1)] for i in range(R+1)]
dp1 = [[0 for j in range(C+1)] for i in range(R+1)]
dp2 = [[0 for j in range(C+1)] for i in range(R+1)]
dp3 = [[0 for j in range(C+1)] for i in range(R+1)]
for i in range(R):
    for j in range(C):
        dp3[i][j] = max(dp3[i][j], dp2[i][j]+I[i][j])
        dp2[i][j] = max(dp2[i][j], dp1[i][j]+I[i][j])
        dp1[i][j] = max(dp1[i][j], dp0[i][j]+I[i][j])
        dp0[i+1][j] = max(dp0[i+1][j], dp0[i][j], dp1[i]
                          [j], dp2[i][j], dp3[i][j])
        dp0[i][j+1] = max(dp0[i][j+1], dp0[i][j])
        dp1[i][j+1] = max(dp1[i][j+1], dp1[i][j])
        dp2[i][j+1] = max(dp2[i][j+1], dp2[i][j])
        dp3[i][j+1] = max(dp3[i][j+1], dp3[i][j])


# print(*dp, sep=' \n')

ans = max(dp0[R-1][C-1], dp1[R-1][C-1], dp2[R-1][C-1], dp3[R-1][C-1])
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
A=sorted(list(map(int,input().split())),reverse=True)
idx=1
for i in range(M):
    value=0

    for m in range(idx):
        if A[m]>value:
            value=A[m]
            nidx=m
    if nidx+1==idx:
        idx+=1
        idx=min(idx,N)
    A[nidx]/=2

A=list(map(int,A))
print(sum(A))


### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A=list(map(lambda x:x*-(1),list(map(int,input().split()))))
heapq.heapify(A)
for i in range(M):
    num=(heapq.heappop(A)*(-1)/2)
    heapq.heappush(A, num*-1)



A=list(map(int,A))
print(-sum(A))
### BUGGY CODE ###

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

import sys

DATA_NUM = 1000000
primes = [2]
for i in range(3, DATA_NUM):
    flag = True
    for p in primes:
         if i % p == 0:
             flag = False
             break
    if flag:
        primes.append(i)
for line in sys.stdin:
    count = 0
    while primes[count] <= int(line):
        count += 1
    print count

### FIXED CODE ###

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

import sys
import math

def countPrimes(n):
    m = int(math.sqrt(n))
    keys = [n/i for i in range(1, m+1)]
    keys += range(keys[-1]-1, 0, -1)
    h = {i:i-1 for i in keys}
    for i in range(2, m+1):
        if h[i] > h[i-1]:
            hp = h[i-1]
            i2 = i*i
            for j in keys:
                if j < i2:
                    break
                h[j] -= h[j/i]-hp
    return h[n]

for line in sys.stdin:
    print countPrimes(int(line))
### BUGGY CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 仕方ないので，numpy で同時代入
# 嫌いだけど def main も使ってみた．
import numpy as np
import sys

def main():
  H, W = list(map(int, input().split()))
  all_in = sys.stdin.readlines()
  all_count = H * W
  blacks = [i*W+j for i in range(H) for j in range(W) if all_in[i][j] == "#"]
  L = np.asarray([False]*all_count)
  L[blacks] = True
  black_count = len(blacks)
 
  cands_H = [-W, W]
  cands_W = [-1, 1]
  result = 0
  while black_count < all_count:
    next_steps = set([black+cand for black in blacks for cand in cands_H]) | set([black+cand for black in blacks for cand in cands_W if black%W not in [0, W-1]])
    blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
    L[blacks] = True
    black_count += len(blacks)
    #print(blacks)
    result += 1

  print(result)

if __name__ == "__main__":
  main()

### FIXED CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
from collections import deque
import copy

def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)

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

def f():
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=[int(j) for j in input().split()]
    #import numpy as np
    #dp=np.zeros((n,n,2),dtype=np.int64)
    dp=[[[0,0]for j in range(n)] for i in range(n)]

    for i in range(1,1+n):
        for j in range(n-i+1):
            #j~j+i-1
            if i==1:
                dp[j][j][1]=a[j]
                continue
            tmp=10**18
            for k in range(i-1):
                #j~j+k,j+k+1~j+i-1
                if sum(dp[j][j+k])+sum(dp[j+k+1][j+i-1])<tmp:
                    tmp=sum(dp[j][j+k])+sum(dp[j+k+1][j+i-1])
                    dp[j][j+i-1][0]=tmp
                    dp[j][j+i-1][1]=dp[j][j+k][1]+dp[j+k+1][j+i-1][1]
    print(dp[0][n-1][0])

f()

### FIXED CODE ###

def f():
    import sys
    import numpy as np
    input=sys.stdin.readline
    n=int(input())
    a=np.array([0]+[int(j) for j in input().split()])
    np.cumsum(a,out=a)
    dp=np.zeros((n,n+1),np.int64)

    for i in range(1,n):
        l=np.arange(n-i)
        r=np.arange(i+1,n+1)
        m=(np.arange(1,i+1)+l[:,np.newaxis]).T
        dp[l,r]=np.amin(dp[l,m]+dp[m,r],0)+a[r]-a[l]
    print(dp[0][n])
f()
### BUGGY CODE ###

import heapq
import math
import random
import sys
import numpy as np


sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    arr = sorted(enumerate(map(int, input().split())),
                 key=lambda x: x[1], reverse=True)
    dp = np.zeros((n+1, n+1), dtype=np.int)

    for i in range(n):
        for j in range(n-i):
            idx, a = arr[i+j]
            dp[i+1, j] = max(dp[i+1, j], dp[i, j] + a*(idx-i))
            dp[i, j+1] = max(dp[i, j+1], dp[i, j] + a*(n-1-j-idx))

    print(max(dp[i, n-i] for i in range(n+1)))


### FIXED CODE ###

import heapq
import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, namedtuple, UserDict
from functools import cmp_to_key, lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)
import numpy as np


sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    arr = sorted(enumerate(map(int, input().split()), 1),
                 key=lambda x: x[1], reverse=True)
    dp = np.zeros(n+1, dtype=np.int)

    for k, (i, a) in enumerate(arr, 1):
        ndp = dp.copy()
        
        add_left = np.abs(np.arange(1, k+1) - i) * a
        ndp[1:k+1] = np.maximum(ndp[1:k+1], dp[:k] + add_left)
        
        add_right = np.abs(np.arange(n-k+1, n+1) - i) * a
        ndp[:k] = np.maximum(ndp[:k], dp[:k] + add_right)

        dp = ndp

    print(dp.max())
### BUGGY CODE ###

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

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


### FIXED CODE ###

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

from itertools import combinations
n, a = map(int, input().split())
X = list(map(int, input().split()))

ans = 0

for i in range(1, n+1):
    L = list(combinations(X, i))
    for l in L:
        if sum(l) / i == a:
            ans += 1
print(ans)


### FIXED CODE ###

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

# dp[i][j][k] i枚までj枚えらんで合計k
# 答えはdp[n][1..n][a..ak]
dp = [[[0] * 2700 for _ in range(52)]
      for __ in range(52)]

dp[0][0][0] = 1
for i in range(0, n):
    for j in range(0, n + 1):
        for k in range(n * max(X) + 1):
            dp[i + 1][j][k] += dp[i][j][k]  # 選ぶ
            dp[i + 1][j + 1][k + X[i]] += dp[i][j][k]  # 選ばない

ans = 0
for i in range(1, n+1):
    for j in range(a, 2501):
        if i * a == j:
            ans += dp[n][i][j]
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
A=[]
B=[]
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    A.append(b)
  if b==n:
    B.append(a)
for i in A:
  if i in B:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

### FIXED CODE ###

n,m=map(int,input().split())
A=[]
B=[]
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    A.append(b)
  if b==n:
    B.append(a)
if len(set(A) & set(B))>0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

#C

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


for i in range(n-1):
    j = a.index(i+1)+1
    print (str(j) + " ", end="")
    
print(a.index(n)+1)

### FIXED CODE ###

#C

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

ans = sorted(range(len(a)), key=lambda k: a[k])

for i in range(n-1):
    print(str(ans[i]+1) + " ",end="")
print(ans[n-1]+1)
### BUGGY CODE ###

import collections

s = input()
r = []

for i in range(len(s)):
    r.append(int(s[i: len(s)]) % 2019)


c = collections.Counter(r)
values = list(c.values())

cnt = 0
for num in values:
    if num < 2:
        continue
    
    cnt += num * (num - 1) // 2
cnt += c[0]

print(cnt)

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2000000001)
ab = abs; mn = min

def solve(n,k,ar,dp,x):
	if x>=n-2: return dp[x]
	if not dp[x] is -1: return dp[x]
	# for i in range(x+1,mn(n,x+k+1)):
	# 	t = ab(ar[x]-ar[i])+solve(n,k,ar,dp,i)
	# 	m = t if t<m else m
	m = mn((ab(ar[x]-ar[i])+solve(n,k,ar,dp,i) for i in range(x+1,mn(n,x+k+1))))
	dp[x] = m
	# pr(f'{x} => {dp[x]}')
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [ab(ar[-2]-ar[-1]),0]
	# pr((n,k,ar,dp))
	pr(solve(n,k,ar,dp,0))

main()

### FIXED CODE ###

import sys
from functools import reduce
sys.setrecursionlimit(2000000001)

def solve(n,k,ar,dp,x):
	ab = abs; mn = min
	if x>=n-2: return dp[x]
	if not dp[x] is -1: return dp[x]
	# t = [ for i in range(x+1,mn(n,x+k+1))]
	t = map(lambda i:ab(ar[x]-ar[i])+solve(n,k,ar,dp,i), range(x+1,mn(n,x+k+1)))
	dp[x] = reduce(lambda a,b : a if a < b else b,t)
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	pr(solve(n,k,ar,dp,0))

main()
### BUGGY CODE ###

N, K, L = map(int, input().split())
G = [[[], []] for i in range(N)]
R = [[i, i] for i in range(N)]
def root(i, j):
  if R[i][j] != i:
    R[i][j] = root(R[i][j], j)
  return R[i][j]
for i in range(K):
  p, q = map(int, input().split())
  rp = root(p - 1, 0)
  rq = root(q - 1, 0)
  if rp != rq:
    R[rp][0] = min(rp, rq)
    R[rq][0] = min(rp, rq)
for i in range(L):
  r, s = map(int, input().split())
  rr = root(r - 1, 1)
  rs = root(s - 1, 1)
  if rr != rs:
    R[rr][1] = min(rr, rs)
    R[rs][1] = min(rr, rs)
U = [[[], []] for i in range(N)]
for i in range(N):
  R[i][0] = root(i, 0)
  R[i][1] = root(i, 1)
  U[R[i][0]][0].append(i)
  U[R[i][1]][1].append(i)
A = [1 for i in range(N)]
for i in range(N):
  if A[i] == 1:
    S = set(U[R[i][0]][0]) & set(U[R[i][1]][1])
    for s in S:
      A[s] = len(S)
ans = ''
for a in A:
  ans += ' ' + str(a)
print(ans[1:])

### FIXED CODE ###

from collections import defaultdict
N, K, L = map(int, input().split())
G = [[[], []] for i in range(N)]
R = [[i, i] for i in range(N)]
def root(i, j):
  if R[i][j] != i:
    R[i][j] = root(R[i][j], j)
  return R[i][j]
for i in range(K):
  p, q = map(int, input().split())
  rp = root(p - 1, 0)
  rq = root(q - 1, 0)
  if rp != rq:
    R[rp][0] = min(rp, rq)
    R[rq][0] = min(rp, rq)
for i in range(L):
  r, s = map(int, input().split())
  rr = root(r - 1, 1)
  rs = root(s - 1, 1)
  if rr != rs:
    R[rr][1] = min(rr, rs)
    R[rs][1] = min(rr, rs)
A = defaultdict(int)
for i in range(N):
  R[i][0] = root(i, 0)
  R[i][1] = root(i, 1)
  A[(R[i][0], R[i][1])] += 1
for i in range(N):
  print(A[(R[i][0], R[i][1])])
### BUGGY CODE ###

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

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

for Ai in A:
    ans *= Ai
    
if ans>10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

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

for Ai in A:
    ans *= Ai
    
    if ans>10**18:
        print(-1)
        exit()
        
print(ans)