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

from queue import Queue

def bfs(point):
    global visit, s
    while point.qsize() > 0:
        hh, ww = point.get()
        if visit[hh][ww] == inf:
            visit[hh][ww] = calc_min(hh, ww)
        h_w_list = [[hh + 1, ww], [hh - 1, ww], [hh, ww + 1], [hh, ww - 1]]
        for h_, w_ in h_w_list:
            if (h_ in range(h)) & (w_ in range(w)):
                if s[h_][w_] == ".":
                    if visit[h_][w_] == inf:                    
                        point.put([h_, w_])
        
        

def calc_min(hh, ww):
    h_w_list = [[hh + 1, ww], [hh - 1, ww], [hh, ww + 1], [hh, ww - 1]]
    min_num = inf
    for h_, w_ in h_w_list:
        if (h_ in range(h)) & (w_ in range(w)):
            min_num = min(min_num, visit[h_][w_])
    return min_num + 1
    
inf = 10 ** 9    
h, w = map(int, input().split())
s = []
point_num = 0
for _ in range(h):
    k = input()
    point_num += k.count(".")
    s.append(list(k))
visit = [[inf for _ in range(w)] for _ in range(h)]
point = Queue()
point.put([0, 0])
visit[0][0] = 0
bfs(point)
ans = point_num - visit[-1][-1] - 1
if ans < 0:
    ans = -1
print(ans)

### FIXED CODE ###

from queue import Queue

def bfs(point):
    global visit, s
    while point.qsize() > 0:
        hh, ww = point.get()
        h_w_list = [[1, 0], [- 1, 0], [0, 1], [0, - 1]]
        for h_, w_ in h_w_list:
            h_ = h_ + hh
            w_ = w_ + ww
            if (h_ in range(h)) & (w_ in range(w)):
                if s[h_][w_] == ".":
                    if visit[h_][w_] == inf:                    
                        point.put([h_, w_])
                        visit[h_][w_] = visit[hh][ww] + 1
        
    
inf = 10 ** 9    
h, w = map(int, input().split())
s = []
point_num = 0
for _ in range(h):
    k = input()
    point_num += k.count(".")
    s.append(list(k))
visit = [[inf for _ in range(w)] for _ in range(h)]
point = Queue()
point.put([0, 0])
visit[0][0] = 0
bfs(point)
ans = point_num - visit[-1][-1] - 1
if ans < 0:
    ans = -1
print(ans)
### BUGGY CODE ###

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

dp = [0] + [1000000000] * (N-1)

for i in range(N-1):
	for j in range(1, K+1):
		if i+j <= N-1:
			dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j] - h[i]))

print(dp[-1])

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))

dp = np.array([0] * N)
#candi = np.array([0] * N)

for i in range(1, N):
	j = max(0, i-K)
	#print()
	#candi[j:i] = dp[j:i] + np.abs(h[i] - h[j:i])
	dp[i] = (dp[j:i] + np.abs(h[i] - h[j:i])).min()
	#print('j,i=',j,i)
	#print('dp[j:i]=',dp[j:i])
	#print('np.abs(h[i] - h[j:i]) = ', np.abs(h[i] - h[j:i]) )		
	#print('candi[j:i]=',candi[j:i])
	#dp[i] = candi[j:i].min()
	#print('dp=',dp)
				
print(dp[-1])
### BUGGY CODE ###

import itertools

n = int(input())
l = [int(v) for v in input().split()]

comb = list(itertools.combinations(l, 3))
count = 0
for i in range(len(comb)):
    a = comb[i][0]
    b = comb[i][1]
    c = comb[i][2]
    if a + b <= c:
        continue
    elif a + c <= b:
        continue
    elif b + c <= a:
        continue
    else:
        count += 1

print(count)

### FIXED CODE ###

import bisect


def triangles():
    n = int(input())
    l = [int(v) for v in input().split()]
    l.sort()

    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            c = l[i] + l[j]
            index = bisect.bisect_left(l, c)
            count += max(index - j - 1, 0)

    print(count)


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

n = int(input())
s = list(input())
turn = 100

for i in range(n):
    a = s[:i]
    b = s[i+1:]
    stock = a.count("W")+b.count("E")
    if turn > stock:
        turn = stock
print(turn)

### FIXED CODE ###

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

ruisekiwa = [0]
ans = n

for i in s:
    if i == "W":
        ruisekiwa.append(ruisekiwa[-1]+1)
    else:
        ruisekiwa.append(ruisekiwa[-1])
        
for i in range(1,n+1):
    w = ruisekiwa[i-1]
    e = n-i-(ruisekiwa[-1]-ruisekiwa[i])
    ans = min(ans,w+e)
    
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  MAX = 998244353
  n, m, k = map(int, input().split())
  
  def pow_mod_p(n, k, p):
    x = 1
    while k:
      if k % 2 == 1:
        x *= n
        x %= p
      n **= 2
      n %= p
      k >>= 1
    return x
  
  ncp = m * pow_mod_p(m-1, n-1, MAX)
  divm = pow_mod_p(m-1, MAX-2, MAX)
  cnt = ncp
  cmb = 1
  for ik in range(1, k+1):
    ncp *= divm
    ncp %= MAX
    
    cmb *= ((n-ik) * pow_mod_p(ik, MAX-2, MAX))
    cmb %= MAX
    
    cnt += ncp * cmb
    cnt %= MAX
    
  print(cnt % MAX)

if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  MAX = 998244353
  n, m, k = map(int, input().split())
    
  cnt = 0
  cmb = 1
  for ik in range(k+1):
    ncp = m * pow(m-1, n-ik-1, MAX)
    ncp %= MAX
    
    if ik == 0:
      cmb = 1
    else:
      cmb *= ((n-ik) * pow(ik, MAX-2, MAX))
    cmb %= MAX
    
    cnt += ncp * cmb
    cnt %= MAX
    
  print(cnt % MAX)

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

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

s = input()

count = []

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

### FIXED CODE ###

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

s = input()

count = [0] * n

for i in range(n) :
    if s[i-1] + s[i] == 'AC' :
        count[i] = count[i-1] + 1
    else :
        count[i] = count[i-1]

for j in range(0, q) :
    l, r = map(int, input().split())
    print(count[r-1] - count[l-1])
### BUGGY CODE ###

from math import sqrt

N = int(input())

ans = 0

for i in range(1,N+1):
    t = sqrt(i)
    #平方数の除外
    if t //1 == t :
        ans += i
        
    j = 1
    while j < t:
        if i%j == 0:
            ans += 2*i
        j += 1
   # print(ans)
print(ans)

### FIXED CODE ###

N = int(input())

ans = 0
for i in range(1, N+1):
    ans += i*(N//i*(N//i+1))//2
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict
from sys import stdin
import copy


def solve():
  ## input
  N = int(input())
  An = [[i-1 for i in list(map(int, stdin.readline().rstrip().split()))] for _ in range(N)]  

  ## solve
  ret = 0
  Pn = [0 for _ in range(N)]
  Rev = set([i for i in range(N)])
  while len(Rev) > 0:
    dct = defaultdict(lambda:set([]))
    game = 0
    for i in copy.deepcopy(Rev):
      if Pn[i] >= N-1:
        continue
      else:
        j = An[i][Pn[i]]
        if i in dct[j]:
          dct[j].remove(i)
          game,Pn[i],Pn[j] = [game+1,Pn[i]+1,Pn[j]+1]
          if Pn[i] >= N-1:
            Rev.remove(i)
          if Pn[j] >= N-1:
            Rev.remove(j)
        else:
          dct[i].add(j)
    if game > 0:
      ret += 1
    else:
      return -1
  return ret

print(solve())


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import deque,defaultdict
from sys import stdin



def solve():
  ## input
  N = int(input())
  An = [deque([i-1 for i in list(map(int, stdin.readline().rstrip().split()))]) for _ in range(N)]

  ## solve
  Pn = set([i for i in range(N)])
  count = 0
  while len(Pn) > 0:
    Qn = set([])
    dct = defaultdict(lambda:set([]))
    for i in Pn:
      j = An[i][0]
      if i in dct[j]:
        An[i].popleft()
        if len(An[i]) > 0:
          Qn.add(i)
          Qn.add(An[i][0])
        An[j].popleft()
        if len(An[j]) > 0:
          Qn.add(j)
          Qn.add(An[j][0])
      else:
        dct[i].add(j)
    Pn = Qn
    count += 1
  for i in range(N):
    if len(An[i]) > 0:
      return -1
  return count



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

import numpy as np

n,m = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for  i in range(0,m):
    max = np.argmax(a)
    a[max] = a[max] // 2

for j in range(0,n):
    ans += a[j]

print(ans)

### FIXED CODE ###

import heapq as hq

n,m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(lambda x: x*(-1), a))
hq.heapify(b)
for  _ in range(0,m):
    max = hq.heappop(b)*(-1)
    max = (-1)*(max // 2)
    hq.heappush(b, max)

print(-sum(b))
### BUGGY CODE ###

import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

from itertools import accumulate, permutations, combinations, takewhile, compress, cycle

# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint
import heapq

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)


# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

def dfs(n):
    if n in to:
        return
    else:
        to.add(n)
        for a, b, c in edges:
            if a == n:
                dfs(b)


def dfs2(n):
    if n in ot:
        return
    else:
        ot.add(n)
        for a, b, c in edges:
            if b == n:
                dfs2(a)


N, M, P = [int(x) for x in input().split()]
edges = []
# 1から行けるノード
to = set()
# N-1に到達できるノード
ot = set()
for _ in range(M):
    a, b, c = [int(x) for x in input().split()]
    a, b, c = a - 1, b - 1, c - P
    edges.append((a, b, -c))

dfs(0)
dfs2(N - 1)

W = [INF] * N
W[0] = 0
for cnt in range(N + 1):
    isShusoku = True
    for a, b, c in edges:
        if b in to and b in ot:
            if W[b] > W[a] + c:
                W[b] = W[a] + c
                isShusoku = False

if isShusoku == True:
    print(max(0,-W[N - 1]))
else:
    print(-1)
pass


### FIXED CODE ###

import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

from itertools import accumulate, permutations, combinations, takewhile, compress, cycle

# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint
import heapq

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)


# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

def dfs(n):
    if n in to:
        return
    else:
        to.add(n)
        for a, b, c in edges:
            if a == n:
                dfs(b)


def dfs2(n):
    if n in ot:
        return
    else:
        ot.add(n)
        for a, b, c in edges:
            if b == n:
                dfs2(a)


N, M, P = [int(x) for x in input().split()]
edges = []
# 1から行けるノード
to = set()
# N-1に到達できるノード
ot = set()
for _ in range(M):
    a, b, c = [int(x) for x in input().split()]
    a, b, c = a - 1, b - 1, c - P
    edges.append((a, b, -c))

dfs(0)
dfs2(N - 1)

W = [INF] * N
W[0] = 0
for cnt in range(N + 1):
    isShusoku = True
    for a, b, c in edges:
        if b in to and b in ot:
            if W[b] > W[a] + c:
                W[b] = W[a] + c
                isShusoku = False

if isShusoku == True:
    print(max(0,-W[N - 1]))
else:
    print(-1)
pass
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
G = []
for i in range(N):
    a = A[i]
    gmax = -1
    for j in range(len(G)):
        if G[j][-1]<a:
            if G[j][-1]>gmax:
                gmax = G[j][-1]
                ind = j
    if gmax>=0:
        G[ind].append(a)
    else:
        G.append([a])
print(len(G))

### FIXED CODE ###

import bisect
from collections import deque
N = int(input())
S = deque([int(input())])
for _ in range(N-1):
    a = int(input())
    ind = bisect.bisect_right(S,a)
    if S[ind-1]==a:
        ind1 = bisect.bisect_left(S,a)
        if ind1>0 and S[ind1-1]<a:
            S[ind1-1]=a
        else:
            S.appendleft(a)
    elif ind==0:
        S.appendleft(a)
    else:
        S[ind-1]=a
#     print("a,S = {}{}".format(a,S))
print(len(S))
### BUGGY CODE ###

N,M = map(int,input().split())
A,B = [],[]
for i in range(N):
  a,b = map(int,input().split())
  A += [a]
  B += [b]
AA = []
BB = []
while True:
  le = len(A)
  if le == 0:
    break
  else:
    for i in range(le):
      mini = min(A)
      if A[i] == mini:
        AA += [A[i]]
        BB += [B[i]]
        del A[i]
        del B[i]
        break
rest = M
cost = 0
while True:
  if rest - BB[0] <= 0:
    cost += rest * AA[0]
    break
  else:
    rest -= BB[0]
    cost += AA[0] * BB[0]
    del AA[0]
    del BB[0]
print(cost)

### FIXED CODE ###

N,M = map(int,input().split())
ab = []
for i in range(N):
  ab += [list(map(int,input().split()))]
ab.sort()
rest = M
cost = 0
while True:
  if rest - ab[0][1] <= 0:
    cost += rest * ab[0][0]
    break
  else:
    rest -= ab[0][1]
    cost += ab[0][0] * ab[0][1]
    del ab[0]
print(cost)
### BUGGY CODE ###

import numpy as np

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

lr_mat = np.zeros((m, 2))

for i in range(m):
    lr_mat[i, :] = list(map(int, input().split()))

cnt = 0
for i in range(n):
    flag = True
    for j in range(m):
        left = lr_mat[j, 0]
        right = lr_mat[j, 1]
        if not ((left <= i+1) and (i+1 <= right)):
            flag = False
            break
    if(flag):
        cnt += 1

print(cnt)


### FIXED CODE ###

import numpy as np

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

lr_mat = np.zeros((m, 2))

for i in range(m):
    lr_mat[i, :] = list(map(int, input().split()))

left_max = max(lr_mat[:, 0])
right_min = min(lr_mat[:, 1])

cnt = 0
for i in range(1, n+1):
    if(left_max <= i) and (i <= right_min):
        cnt += 1

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

import sys
readline = sys.stdin.readline

N,K = map(int, readline().split())
A = list(map(int,readline().split()))
DIV = 10 ** 9 + 7

# dp[i][j] : i人目までにj個配るときの場合の数
# 数式変形で以下
# dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - Ai-1 - 1]

dp = [[0] * (K + 1) for i in range(N + 1)]
for i in range(N + 1):
  dp[i][0] = 1 # 0個配る方法は常に1通り
  
for i in range(1, N + 1):
  for j in range(1, K + 1):
    if j - A[i - 1] - 1 >= 0:
      dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - A[i - 1] - 1]) % DIV
    else:
      dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % DIV
      
print(dp[N][K])

### FIXED CODE ###

import sys
readline = sys.stdin.readline

N,K = map(int, readline().split())
A = list(map(int,readline().split()))
DIV = 10 ** 9 + 7

# dp[i][j] : i人目までにj個配るときの場合の数
# 数式変形で以下
# dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - Ai-1 - 1]

dp = [[0] * (K + 1) for i in range(N + 1)]
for i in range(N + 1):
  dp[i][0] = 1 # 0個配る方法は常に1通り
  
for i in range(1, N + 1):
  for j in range(1, K + 1):
    if j - A[i - 1] - 1 >= 0:
      dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - A[i - 1] - 1]) % DIV
    else:
      dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % DIV
      
print(dp[N][K])
### BUGGY CODE ###

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

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

### FIXED CODE ###

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

l = sorted(range(len(a)), key=a.__getitem__)
for i in l:
    print(i + 1, end = " ")
### BUGGY CODE ###

import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N = I()
A = LI()
A = sorted(A)

B = [0]*(10**6+1)
C = [0]*(10**6+1)
for i in range(len(A)):
    if B[A[i]] == 0:
        C[A[i]] = 1
    for j in range(A[i]*2,10**6+1,A[i]):
        B[j] = 1

from collections import Counter

c = Counter(A)

for i in c.keys():
    if c[i] >= 2:
        C[i] = 0

print(sum(C))

### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
A = LI()
A = sorted(A)

if N == 1:
    print(1)
    exit()

if A[0] == 1:
    if N >= 2 and A[1] == 1:
        print(0)
        exit()
    else:
        print(1)
        exit()

B = [0]*(10**6+1)
C = [0]*(10**6+1)
for i in range(len(A)):
    if B[A[i]] == 0:
        C[A[i]] = 1
    for j in range(A[i]*2,10**6+1,A[i]):
        B[j] = 1

from collections import Counter

c = Counter(A)

for i in c.keys():
    if c[i] >= 2:
        C[i] = 0

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

N = int(input())
a = list(map(int, input().split()))
diff = []
for i in range(N-1):
    diff.append(abs(sum(a[:i+1]) - sum(a[i+1:])))
print(min(diff))


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
sunuke = []
diff = []
total = sum(a)
for i, x in enumerate(a[0:-1]):
    if(i==0):
        sunuke.append(x)
    else:
        sunuke.append(x + sunuke[i-1])
for i in sunuke:
    diff.append(abs((i * 2) - total))
print(min(diff))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = []
for i in range(N):
    ans.append(A.index(i+1)+1)

print(*ans)


### FIXED CODE ###

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

out = [0] * N

for i in range(N):
    out[A[i] - 1] = i + 1
print(*out)
### BUGGY CODE ###

import sys
# input処理を高速化する
input = sys.stdin.readline

def main():
    N = int(input())
    lst_p = list(map(float, input().split()))
    # dp[i][j] := 最初の i 枚のコインを投げたときに、表が j 枚となる確率
    # 次のコインが表: dp[i+1][j+1] += dp[i][j]∗p[i]
    # 次のコインが裏: dp[i+1][j] += dp[i][j]∗(1.0−p[i])
    dp = [[0] * (N+1) for i in range(N+1)]
    # 初期条件
    dp[0][0] = 1.0
    for i in range(N):
        for j in range(N):
            dp[i+1][j+1] += dp[i][j] * lst_p[i]
            dp[i+1][j] += dp[i][j] * (1.0 - lst_p[i])
    
    ans = 0
    for i in range((N+1)//2, N+1):
        ans += dp[N][i]
    print(ans)
main()

### FIXED CODE ###

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

dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1
# dp[i][j]:i番目以前の商品を見たときに表の枚数がj枚となる確率の和

for i in range(1,n+1):
    for j in range(i+1):
            dp[i][j] = dp[i-1][j]*(1-p[i-1])
            if j>0:
                dp[i][j] += dp[i-1][j-1]*p[i-1]

ans = sum(dp[n][(n+1)//2:])

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

N = int(input())
Alist = [int(x) for x in input().split()]
invans = 0
for i in range(N):
    for j in range(N):
        if i == j:
            None
        else:
            if Alist[i] % Alist[j] == 0:
                invans += 1
                break

print(N - invans)

### FIXED CODE ###

N = int(input())
Alist = [int(x) for x in input().split()]
M = max(Alist)
A0 = ['NotUse']
Abool = A0 + [0 for x in range(M)]
Alist.sort()
ans = 0

for i in Alist:
    for j in range(i,M+1,i):
        if Abool[j] >= 2:
            None
        else:
            Abool[j] += 1
    
for i in Alist:
    if Abool[i] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

def numerator(x):
    return x * (x + 1) // 2

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

ACC = 1
for p in P:
    ACC *= p

R = 0
for p in P[:K]:
    R += numerator(p) * ACC // p

max_value = R
for i in range(N-K):
    R += numerator(P[i+K]) * ACC // P[i+K] - numerator(P[i]) * ACC // P[i]
    max_value = max(max_value, R)
print(max_value / ACC)

### FIXED CODE ###

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

#期待値 : (p+1)//2
range_total = sum(P[:K]) + K
max_value = range_total
for i in range(N-K):
    range_total += P[K+i] - P[i]
    max_value = max(max_value, range_total)
print(max_value / 2)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def solve(N: int, a: "List[int]"):
    dpmin = [[None] * (N + 1) for _ in range(N + 1)]
    dpmax = [[None] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dpmin[i][i] = dpmax[i][i] = 0
    for i in range(N):
        dpmin[i][i + 1] = -a[i]
        dpmax[i][i + 1] = a[i]

    def minimize(a, begin, end):
        x = dpmin[begin][end]
        if x is not None:
            return x
        pt1 = -a[begin] + maximize(a, begin + 1, end)
        pt2 = -a[end - 1] + maximize(a, begin, end - 1)
        r = min(pt1, pt2)
        dpmin[begin][end] = r
        return r

    def maximize(a, begin, end):
        x = dpmax[begin][end]
        if x is not None:
            return x
        pt1 = a[begin] + minimize(a, begin + 1, end)
        pt2 = a[end - 1] + minimize(a, begin, end - 1)
        r = max(pt1, pt2)
        dpmax[begin][end] = r
        return r

    return maximize(a, 0, N)


def main():
    N = int(readline())  # type: int
    a = [int(x) for x in readline().split()]  # type: "List[int]"
    print(solve(N, a))


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def solve(N: int, a: "List[int]"):
    N1 = N + 1
    dpmin = [-1] * N1 ** 2
    dpmax = [-1] * N1 ** 2
    for i in range(N1):
        dpmin[0 * N1 + i] = dpmax[0 * N1 + i] = 0
    for i in range(N):
        dpmin[1 * N1 + i] = -a[i]
        dpmax[1 * N1 + i] = a[i]
    for k in range(2, N1):
        for i in range(N - k + 1):
            dpmin[k * N1 + i] = min(
                -a[i] + dpmax[(k - 1) * N1 + i + 1],
                -a[i + k - 1] + dpmax[(k - 1) * N1 + i],
            )
            r = -1
            dpmax[k * N1 + i] = max(
                a[i] + dpmin[(k - 1) * N1 + i + 1],
                a[i + k - 1] + dpmin[(k - 1) * N1 + i],
            )
    return dpmax[N * N1]


def main():
    N = int(readline())  # type: int
    a = [int(x) for x in readline().split()]  # type: "List[int]"
    print(solve(N, a))


if __name__ == "__main__":
    main()