CodeEff/ECCO huggingface dataset:
# Original solution
# dp[j][i]=(区間[i,j]が残っているとき次の手番の得点-そうじゃない人の得点)
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(eval(input()))
a=list(map(int,input().split()))
INF=-10**14
dp=[[0]*(i+1) for i in range(n)]
for i in range(n):
    dp[i][i]=a[i]
for i in range(1,n):
    for j in range(i-1,-1,-1):
        dp[i][j]=max(a[i]-dp[i-1][j],a[j]-dp[i][j+1])
print((dp[-1][0]))

# Optimized solution
import sys
input = sys.stdin.readline
n=int(eval(input()))
a=list(map(int,input().split()))
dp=[0]*3000
for i in range(n):
    dp[i]=a[i]
for i in range(1,n):
    for j in range(i-1,-1,-1):
        dp[j]=max(a[i]-dp[j],a[j]-dp[j+1])
print((dp[0]))
# Original solution
import sys
input = sys.stdin.readline
n=int(eval(input()))
a=list(map(int,input().split()))
dp=[0]*3000
for i in range(n):
    dp[i]=a[i]
for i in range(1,n):
    for j in range(i-1,-1,-1):
        dp[j]=max(a[i]-dp[j],a[j]-dp[j+1])
print((dp[0]))

# Optimized solution
def solve():
    import sys
    input = sys.stdin.readline
    n=int(eval(input()))
    a=list(map(int,input().split()))
    dp=a[:]
    for i in range(1,n):
        for j in range(i-1,-1,-1):
            dp[j]=max(a[i]-dp[j],a[j]-dp[j+1])
    print((dp[0]))
solve()
# Original solution
import sys
sys.setrecursionlimit(10**5)

N = int(eval(input()))
*A, = list(map(int, input().split()))
memo = [[-1]*(N+1) for i in range(N+1)]
for i in range(N+1):
    memo[i][i] = 0
def dfs(p, q, t):
    if memo[p][q] != -1:
        return memo[p][q]
    if t:
        r = min(dfs(p+1, q, 0) - A[p], dfs(p, q-1, 0) - A[q-1])
    else:
        r = max(dfs(p+1, q, 1) + A[p], dfs(p, q-1, 1) + A[q-1])
    memo[p][q] = r
    return r

print((dfs(0, N, 0)))

# Optimized solution
N = int(eval(input()))
*A, = list(map(int, input().split()))
dp = [[-1]*(N+1-i) for i in range(N+1)]
for i in range(N+1):
    dp[0][i] = 0
t = (N & 1)
for l in range(1, N+1):
    S = dp[l-1]; T = dp[l]
    t ^= 1
    if t:
        T[:] = (min(S[i+1] - A[i], S[i] - A[i+l-1]) for i in range(N-l+1))
    else:
        T[:] = (max(S[i+1] + A[i], S[i] + A[i+l-1]) for i in range(N-l+1))
print((dp[N][0]))
# Original solution
N = int(eval(input()))
*A, = list(map(int, input().split()))
dp = [[-1]*(N+1-i) for i in range(N+1)]
for i in range(N+1):
    dp[0][i] = 0
t = (N & 1)
for l in range(1, N+1):
    S = dp[l-1]; T = dp[l]
    t ^= 1
    T[:] = (min(S[i+1] - A[i], S[i] - A[i+l-1]) for i in range(N-l+1)) if t else  (max(S[i+1] + A[i], S[i] + A[i+l-1]) for i in range(N-l+1))
print((T[0]))

# Optimized solution
N = int(eval(input()))
*A, = list(map(int, input().split()))
t = (N & 1)
S = [0]*(N+1)
for l in range(1, N+1):
    S = [min(S[i+1] - A[i], S[i] - A[i+l-1]) for i in range(N-l+1)] if (l ^ N) & 1 else [max(S[i+1] + A[i], S[i] + A[i+l-1]) for i in range(N-l+1)]
print((S[0]))
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
dp=[[float("inf")]*(n+1) for _ in range(n)]
z=0
for l in range(n):
    dp[l][l]=0
for k in range(1,n+1):
    for i in range(n):
        j=i+k
        if 0<=i<=n-2 and 1<=j<=n:
            if (n-(i+j))%2==0: #先手
                dp[i][j]=max(dp[i+1][j]+a[i],dp[i][j-1]+a[j-1])
            else:
                dp[i][j]=min(dp[i+1][j]-a[i],dp[i][j-1]-a[j-1])
        elif 0<=i<=n-2 and 0<=j<=n:
            dp[i][j]=dp[i+1][j]+a[i]
        elif 0<=i<=n-1 and 1<=j<=n:
            dp[i][j]=dp[i][j-1]+a[j-1]
        else:
            z=1

print((dp[0][n]))

# Optimized solution
n=int(eval(input()))
a=list(map(int,input().split()))
dp=[[float("inf")]*(n+1) for _ in range(n)]
z=0
for l in range(n):
    dp[l][l]=0
for k in range(1,n+1):
    for i in range(n-k+1):
        j=i+k
        if 0<=i<=n-2 and 1<=j<=n:
            if (n-(i+j))%2==0: #先手
                dp[i][j]=max(dp[i+1][j]+a[i],dp[i][j-1]+a[j-1])
            else:
                dp[i][j]=min(dp[i+1][j]-a[i],dp[i][j-1]-a[j-1])
        else:
            dp[i][j]=dp[i][j-1]+a[j-1]
print((dp[0][n]))
# Original solution
import sys
def input():
    return sys.stdin.readline()[:-1]

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

dp=[]
for i in range(n):
	dp.append([0]*n)
for i in range(n):
    dp[i][i] = a[i]

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

print((dp[0][n - 1]))

# Optimized solution
import sys
def input():
    return sys.stdin.readline()[:-1]

n = int(eval(input()))
a = [int(x) for x in input().split()]

dp=[]
for i in range(n):
	dp.append([0]*n)
for i in range(n):
    dp[i][i] = a[i]

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

print((dp[0][n - 1]))
# Original solution
import sys
def input():
    return sys.stdin.readline()[:-1]

n = int(eval(input()))
a = [int(x) for x in input().split()]

dp=[]
for i in range(n):
	dp.append([0]*n)
for i in range(n):
    dp[i][i] = a[i]

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

print((dp[0][n - 1]))

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))

def calc():
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]

    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
    return dp

dp = calc()
print((dp[0][n - 1]))
# Original solution
def main():
    n = int(eval(input()))
    a = list(map(int, input().split()))
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
 
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
    print((dp[0][n - 1]))
main()

# Optimized solution
def main():
    n = int(eval(input()))
    a = list(map(int, input().split()))
    dp = [0] * (n*n)
    for i in range(n):
        dp[i+i*n] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            dp[i+j*n] = max(a[i] - dp[i + 1+j*n], a[j] - dp[i+(j - 1)*n])
    print((dp[(n - 1)*n]))
main()
# Original solution
from functools import lru_cache
N = int(eval(input()))
A = list(map(int, input().split()))
import sys
sys.setrecursionlimit(100000)

import random
#N = 20
#A = [random.randint(1, 10**9) for _ in range(N)]


@lru_cache(maxsize=None)
def f(l, r):
  if l > r:
    return 0
  
  n = r - l
  if (N - n) % 2 == 0:
    s = -1
  else:
    s = 1
    
  lv = f(l+1, r) + s*A[l]
  rv = f(l, r-1) + s*A[r]
  
  if s*lv > s*rv:
    return lv
  else:
    return rv
    
   
print((f(0, N-1)))


# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
#import random
#N = 3000
#A = [random.randint(1, 10**9) for _ in range(N)]


dp = [[0] * (N+1) for _ in range(N+1)]
for g in range(N):
  for l in range(N-g):
    r = l + g
    n = r - l
    s = -1 if (N-n) % 2 == 0 else 1
    lv = dp[l+1][r] + s*A[l]
    rv = dp[l][r-1] + s*A[r]
    if s*lv > s*rv:
      dp[l][r] = lv
    else:
      dp[l][r] = rv

print((dp[0][N-1]))
# Original solution
def kukan(n, a):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            L = a[i] - dp[i + 1][j]
            R = a[j] - dp[i][j - 1]
            dp[i][j] = L if L > R else R
    return dp[0][n - 1]


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


# Optimized solution
def kukan(n, a):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        g0 = dp[i]
        g1 = dp[i + 1]
        for j in range(i + 1, n):
            L = a[i] - g1[j]
            R = a[j] - g0[j - 1]
            dp[i][j] = L if L > R else R
    return dp[0][n - 1]


n = int(eval(input()))
a = list(map(int, input().split()))
print((kukan(n, a)))
# Original solution
import sys
sys.setrecursionlimit(10**9)

def recursive(i,j):
  if i>j:
    return 0
  elif dp.get((i,j)):
    return dp[(i,j)]
  dp[(i,j)]=max(nums[i]-recursive(i+1,j),nums[j]-recursive(i,j-1))
  return dp[(i,j)]

dp={}
n=int(eval(input()))
nums=list(map(int,input().split()))
#print(dp)
print((recursive(0,n-1)))



# Optimized solution
dp={}
n=int(eval(input()))
nums=list(map(int,input().split()))
#print(dp)
#print(recursive(0,n-1))
dp=[[0]*(n+1) for _ in range(n+1)]
for i in range(n-1,-1,-1):
    for j in range(i,n,1):
        dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])
print((dp[0][n-1]))
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from functools import lru_cache
def resolve():
    n = int(eval(input()))
    A = list(map(int, input().split()))

    @lru_cache(None)
    def dfs(l, r):
        # base case
        if l == r:
            return 0

        turn = (n - (r - l)) & 1
        if turn & 1 == 0: # first
            return max(A[l] + dfs(l + 1, r), A[r - 1] + dfs(l, r - 1))
        else: # second
            return min(-A[l] + dfs(l + 1, r), -A[r - 1] + dfs(l, r - 1))

    print((dfs(0, n)))
resolve()

# Optimized solution
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from functools import lru_cache
def resolve():
    n = int(eval(input()))
    A = list(map(int, input().split()))

    dp = [[None] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][i] = 0

    for width in range(1, n + 1):
        for l in range(n):
            r = l + width
            if r > n:
                break
            turn = (n - (r - l)) & 1
            if turn & 1 == 0:
                dp[l][r] = max(A[l] + dp[l + 1][r], A[r - 1] + dp[l][r - 1])
            else:
                dp[l][r] = min(-A[l] + dp[l + 1][r], -A[r - 1] + dp[l][r - 1])


    print((dp[0][n]))
resolve()
# Original solution
# input
N = int(eval(input()))
As = list(map(int, input().split()))

# Nの偶奇。区間幅がNの偶奇と一致すれば太郎君目線
oe = N % 2

# def print_list(lis):
#   for l in lis:
#     print(l)


# score[i][j][p] : Asのi番目を左端、j番目を右端とした時の最終スコア
#                  p = 0 が太郎君目線、p = 1 が次郎くん目線
score = [[[None for _ in range(2)] for _ in range(N)] for _ in range(N)]

for i in range(N):
  # 初期化
  # 区間長さ0であれば1通りしかない
  score[i][i][0] = As[i]
  score[i][i][1] = -As[i]

# print_list(score)

for k in range(1, N):
  # 配列の幅を広げながら計算を進める
  for i in range(0, N-k):
    # if k == 0:
    #   continue
    j = i + k
    if i == N - 1:
      if (k + 1) % 2 == oe:
        score[i][j][0] = score[i][j-1][1] + As[j]
      else:
        score[i][j][1] = score[i][j-1][0] - As[j]
    else:
      # print(i,j)
      if (k + 1) % 2 == oe:
        score[i][j][0] = max(score[i+1][j][1] + As[i], score[i][j-1][1] + As[j])
      else:
        score[i][j][1] = min(score[i+1][j][0] - As[i], score[i][j-1][0] - As[j])
    # print_list(score)

print((score[0][N-1][0]))


# Optimized solution
# input
N = int(eval(input()))
As = list(map(int, input().split()))

# Nの偶奇。区間幅がNの偶奇と一致すれば太郎君目線
oe = N % 2

# def print_list(lis):
#   for l in lis:
#     print(l)


# score[i][j][p] : Asのi番目を左端、j番目を右端とした時の最終スコア
#                  p = 0 が太郎君目線、p = 1 が次郎くん目線
score = [[None for _ in range(N)] for _ in range(N)]

for i in range(N):
  # 初期化
  # 区間長さ1であれば1通りしかない
  if oe == 1:
    score[i][i] = As[i]
  else:
    score[i][i] = -As[i]

# print_list(score)

for k in range(1, N):
  # 配列の幅を広げながら計算を進める
  for i in range(0, N-k):
    # if k == 0:
    #   continue
    j = i + k
    if i == N - 1:
      if (k + 1) % 2 == oe:
        score[i][j] = score[i][j-1] + As[j]
      else:
        score[i][j] = score[i][j-1] - As[j]
    else:
      # print(i,j)
      if (k + 1) % 2 == oe:
        score[i][j] = max(score[i+1][j] + As[i], score[i][j-1] + As[j])
      else:
        score[i][j] = min(score[i+1][j] - As[i], score[i][j-1] - As[j])
    # print_list(score)

print((score[0][N-1]))
# Original solution
# input
N = int(eval(input()))
As = list(map(int, input().split()))

# Nの偶奇。区間幅がNの偶奇と一致すれば太郎君目線
oe = N % 2

# def print_list(lis):
#   for l in lis:
#     print(l)


# score[i][j][p] : Asのi番目を左端、j番目を右端とした時の最終スコア
#                  p = 0 が太郎君目線、p = 1 が次郎くん目線
score = [[None for _ in range(N)] for _ in range(N)]

for i in range(N):
  # 初期化
  # 区間長さ1であれば1通りしかない
  if oe == 1:
    score[i][i] = As[i]
  else:
    score[i][i] = -As[i]

# print_list(score)

for k in range(1, N):
  # 配列の幅を広げながら計算を進める
  for i in range(0, N-k):
    # if k == 0:
    #   continue
    j = i + k
    if i == N - 1:
      if (k + 1) % 2 == oe:
        score[i][j] = score[i][j-1] + As[j]
      else:
        score[i][j] = score[i][j-1] - As[j]
    else:
      # print(i,j)
      if (k + 1) % 2 == oe:
        score[i][j] = max(score[i+1][j] + As[i], score[i][j-1] + As[j])
      else:
        score[i][j] = min(score[i+1][j] - As[i], score[i][j-1] - As[j])
    # print_list(score)

print((score[0][N-1]))


# Optimized solution
# input
N = int(eval(input()))
As = list(map(int, input().split()))

# Nの偶奇。区間幅がNの偶奇と一致すれば太郎君目線
oe = N % 2

# def print_list(lis):
#   for l in lis:
#     print(l)


# score[i][j][p] : Asのi番目を左端、j番目を右端とした時の最終スコア
#                  p = 0 が太郎君目線、p = 1 が次郎くん目線
score = [[0 for _ in range(N)] for _ in range(N)]

for i in range(N):
  # 初期化
  # 区間長さ1であれば1通りしかない
  if oe == 1:
    score[i][i] = As[i]
  else:
    score[i][i] = -As[i]

# print_list(score)

for k in range(1, N):
  # 配列の幅を広げながら計算を進める
  for i in range(0, N-k):
    # if k == 0:
    #   continue
    j = i + k
    if i == N - 1:
      if (k + 1) % 2 == oe:
        score[i][j] = score[i][j-1] + As[j]
      else:
        score[i][j] = score[i][j-1] - As[j]
    else:
      # print(i,j)
      if (k + 1) % 2 == oe:
        score[i][j] = max(score[i+1][j] + As[i], score[i][j-1] + As[j])
      else:
        score[i][j] = min(score[i+1][j] - As[i], score[i][j-1] - As[j])
    # print_list(score)

print((score[0][N-1]))
# Original solution
#L
import sys
sys.setrecursionlimit(10**5)

N=int(eval(input()))
a=list(map(int,input().split()))

S=[0]*(N+1)
for i in range(N):
    S[i+1]=S[i]+a[i]

dp=[[0]*(N+1) for _ in range(N+1)]#[l,r)の範囲が残っているときに取れる最大値

def rep(l,r):
    if l==r:
        return 0
    if dp[l][r]!=0:
        return dp[l][r]
    else:
        x=a[l]+(S[r]-S[l+1] - rep(l+1,r))
        y=a[r-1]+(S[r-1]-S[l] - rep(l,r-1))
        dp[l][r]=max(x,y)
        return dp[l][r]
    
    
rep(0,N)
print((2*dp[0][N] - S[-1] ))








# Optimized solution
#L

N=int(eval(input()))
a=list(map(int,input().split()))

S=[0]*(N+1)
for i in range(N):
    S[i+1]=S[i]+a[i]

dp=[[0]*(N+1) for _ in range(N+1)]#[l,r)の範囲が残っているときに取れる最大値

for i in range(1,N+1):#r-lの値
    for j in range(N):#lの値
        r=j+i
        if r>N:
            break
        l=j
        x=a[l]+(S[r]-S[l+1]) - dp[l+1][r]
        y=a[r-1]+(S[r-1]-S[l]) - dp[l][r-1]
        dp[l][r]=max(x,y)

print((2*dp[0][N] - S[-1] ))
# Original solution
def solve():
    n = int(eval(input()))
    a = list(int(x) for x in input().split())

    memo = [[None] * n for _ in range(n)]
    for i, aa in enumerate(a):
        memo[i][i] = aa

    for l in range(n - 2, -1, -1):
        for r in range(l + 1, n):
            memo[l][r] = max(a[r] - memo[l][r - 1], a[l] - memo[l + 1][r])

    print((memo[0][n - 1]))


if __name__ == '__main__':
    solve()

# [l,r]を
# l:=配列aの右端から左にシフト
# r:=lと一致する位置からn-1まで右にシフト
# と考えると、l==rは既にメモ化済みなので、l=n-2以前、r=l+1以降を調べればよい
# 漸化式で使う値は、
# lがより右にいるときの計算結果（前のループで計算済み）と
# rがより左にいるときの計算結果（一番左でもl==rなので計算済み）
# なので、参照する値がNoneになることはなく、Noneのチェックは不要になる

# listにした


# Optimized solution
def solve():
    n = int(eval(input()))
    a = tuple(int(x) for x in input().split())

    memo = tuple([None] * n for _ in range(n))
    for i in range(n):
        memo[i][i] = a[i]

    for l in range(n - 2, -1, -1):
        for r in range(l + 1, n):
            memo[l][r] = max(a[r] - memo[l][r - 1], a[l] - memo[l + 1][r])

    print((memo[0][n - 1]))


if __name__ == '__main__':
    solve()

# [l,r]を
# l:=配列aの右端から左にシフト
# r:=lと一致する位置からn-1まで右にシフト
# と考えると、l==rは既にメモ化済みなので、l=n-2以前、r=l+1以降を調べればよい
# 漸化式で使う値は、
# lがより右にいるときの計算結果（前のループで計算済み）と
# rがより左にいるときの計算結果（一番左でもl==rなので計算済み）
# なので、参照する値がNoneになることはなく、Noneのチェックは不要になる

# enumerateを辞めた
# Original solution
def solve():
    n = int(eval(input()))
    a = tuple(int(x) for x in input().split())

    memo = tuple([None] * n for _ in range(n))
    for i in range(n):
        memo[i][i] = a[i]

    for l in range(n - 2, -1, -1):
        for r in range(l + 1, n):
            memo[l][r] = max(a[r] - memo[l][r - 1], a[l] - memo[l + 1][r])

    print((memo[0][n - 1]))


if __name__ == '__main__':
    solve()

# [l,r]を
# l:=配列aの右端から左にシフト
# r:=lと一致する位置からn-1まで右にシフト
# と考えると、l==rは既にメモ化済みなので、l=n-2以前、r=l+1以降を調べればよい
# 漸化式で使う値は、
# lがより右にいるときの計算結果（前のループで計算済み）と
# rがより左にいるときの計算結果（一番左でもl==rなので計算済み）
# なので、参照する値がNoneになることはなく、Noneのチェックは不要になる

# enumerateを辞めた


# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = a[i]

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

print((dp[0][n - 1]))

# 下記提出と全く同じ内容で提出します
# https://atcoder.jp/contests/dp/submissions/6590284

# これまでの連投で参考にしていたコード
# ほぼ同じ内容で提出しているつもりなのに、速度差が一向に縮まらない

# maxの引数の順番が自分と違うのが速度差の原因？
# Original solution
n = int(eval(input()))
a = tuple(int(x) for x in input().split())

memo = tuple([None] * n for _ in range(n))
for i in range(n):
    memo[i][i] = a[i]

for l in range(n - 2, -1, -1):
    for r in range(l + 1, n):
        memo[l][r] = max(a[l] - memo[l + 1][r], a[r] - memo[l][r - 1])

print((memo[0][n - 1]))

# [l,r]を
# l:=配列aの右端から左にシフト
# r:=lと一致する位置からn-1まで右にシフト
# と考えると、l==rは既にメモ化済みなので、l=n-2以前、r=l+1以降を調べればよい
# 漸化式で使う値は、
# lがより右にいるときの計算結果（前のループで計算済み）と
# rがより左にいるときの計算結果（一番左でもl==rなので計算済み）
# なので、参照する値がNoneになることはなく、Noneのチェックは不要になる

# if __name__ == '__main__':を辞めた


# Optimized solution
def main():
    n = int(eval(input()))
    a = tuple(int(x) for x in input().split())

    memo = tuple([None] * n for _ in range(n))
    for i in range(n):
        memo[i][i] = a[i]

    for l in range(n - 2, -1, -1):
        for r in range(l + 1, n):
            memo[l][r] = max(a[l] - memo[l + 1][r], a[r] - memo[l][r - 1])

    print((memo[0][n - 1]))


if __name__ == '__main__':
    main()

# [l,r]を
# l:=配列aの右端から左にシフト
# r:=lと一致する位置からn-1まで右にシフト
# と考えると、l==rは既にメモ化済みなので、l=n-2以前、r=l+1以降を調べればよい
# 漸化式で使う値は、
# lがより右にいるときの計算結果（前のループで計算済み）と
# rがより左にいるときの計算結果（一番左でもl==rなので計算済み）
# なので、参照する値がNoneになることはなく、Noneのチェックは不要になる

# 関数名は関係あるのか？
# Original solution
def fun(i,j):
	# print(i,j)
	if i>j or i>=n or j<0:
		return 0
	elif i==j:
		dp[i][j]=arr[i]
		return dp[i][j]
	else:
		if dp[i][j]==0:
			dp[i][j]=max(arr[i]+min(fun(i+1,j-1),fun(i+2,j)),arr[j]+min(fun(i+1,j-1),fun(i,j-2)))
		return dp[i][j]
n=int(eval(input()))
dp=[0]*n
for i in range(n):
	dp[i]=[0]*n
arr=list(map(int,input().split()))
print((2*fun(0,n-1)-sum(arr)))

# Optimized solution
def fun(i,j):
	# print(i,j)
	if i>j or i>=n or j<0:
		return 0
	elif i==j:
		dp[i][j]=arr[i]
		return dp[i][j]
	else:
		if dp[i][j]==0:
			dp[i][j]=max(arr[i]+min(fun(i+1,j-1),fun(i+2,j)),arr[j]+min(fun(i+1,j-1),fun(i,j-2)))
		return dp[i][j]
n=int(eval(input()))
dp=[0]*n
for i in range(n):
	dp[i]=[0]*n
arr=list(map(int,input().split()))

for i in range(n-1,-1,-1):
	for j in range(i,n,1):
		if i==j:
			dp[i][j]=arr[i]
		else:
			dp[i][j]=max(arr[i]-dp[i+1][j],arr[j]-dp[i][j-1])
		# print(dp[i])
print((dp[0][n-1]))
# print(2*fun(0,n-1)-sum(arr))
# Original solution
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
aN = LIST()

# メモ[左端位置][右端位置] = この局面からの結果
memo = [[None] * (N+1) for i in range(N+1)]

def dfs(l, r):
    # 全部取り切ったので終了
    if l > r:
        return 0
    # 既に見た局面ならメモの内容を返す
    if memo[l][r] is not None:
        return memo[l][r]
    turn = 0 if N % 2 != (r-l) % 2 else 1
    # 先手番
    if turn == 0:
        mx = -INF
        mx = max(mx, dfs(l+1, r) + aN[l])
        mx = max(mx, dfs(l, r-1) + aN[r])
        # ここより深い所を探し終わったので結果をメモする
        memo[l][r] = mx
        return mx
    # 後手番
    else:
        mn = INF
        mn = min(mn, dfs(l+1, r) - aN[l])
        mn = min(mn, dfs(l, r-1) - aN[r])
        memo[l][r] = mn
        return mn

print((dfs(0, N-1)))


# Optimized solution
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

# dp[i][j] := 左からi個、右からj個取った状態での最大(最小)得点
dp = list2d(N+1, N+1, 0)
# 初期化：どちらの手番で使う場所かに合わせて-INFかINFにする
for i in range(N):
    turn = i & 1
    for j in range(i+1):
        k = i - j
        if turn == 0:
            dp[j][k] = -INF
        else:
            dp[j][k] = INF
# 最初の遷移の開始地点(ゲーム終了の状態)は0に
for i in range(N+1):
    dp[i][N-i] = 0
# 終了から順番に戻って見ていく
for i in range(N-1, -1, -1):
    turn = i & 1
    for j in range(i+1):
        k = i - j
        l = j
        r = N - 1 - k
        if turn == 0:
            # 先手番の遷移
            dp[j][k] = max(dp[j][k], dp[j+1][k] + A[l])
            dp[j][k] = max(dp[j][k], dp[j][k+1] + A[r])
        else:
            # 後手番の遷移
            dp[j][k] = min(dp[j][k], dp[j+1][k] - A[l])
            dp[j][k] = min(dp[j][k], dp[j][k+1] - A[r])
ans = dp[0][0]
print(ans)
# Original solution
def deque(a):
    n = len(a)
    cur = [(x, 0) for x in a]
    nxt = [(0, 0)] * n
    for l in range(2, n + 1):
        for i in range(n - l + 1):
            j = i + l - 1
            x, y = cur[i]
            z, t = cur[i + 1]
            if a[i] + t - z > a[j] + y - x:
                nxt[i] = (a[i] + t, z)
            else:
                nxt[i] = (a[j] + y, x)
        cur, nxt = nxt, cur
    return cur[0][0] - cur[0][1]


def main():
    eval(input())  # n
    a = [int(x) for x in input().split()]
    return deque(a)


print((main()))


# Optimized solution
def deque(a):
    n = len(a)
    cur = a[:]
    nxt = [0] * (n - 1)
    for l in range(2, n + 1):
        for i in range(n - l + 1):
            j = i + l - 1
            nxt[i] = max(a[i] - cur[i + 1], a[j] - cur[i])
        cur, nxt = nxt, cur
    return cur[0]


def main():
    eval(input())  # n
    a = [int(x) for x in input().split()]
    return deque(a)


print((main()))