CodeEff/ECCO huggingface dataset:
# Original solution
import sys
sys.setrecursionlimit(1000000)


N=eval(input())
A=list(map(int, sys.stdin.readline().split()))

dp=[ [ 0 for i in range(N) ]  for j in range(N) ]

def func(x,y,cnt):
	if dp[x][y]>0: return dp[x][y]
	ret=0
	if x==y:
		if cnt%2==0:
			ret=A[x]
			dp[x][y]=ret
			return ret
		else:
			ret=-1*A[x]
			dp[x][y]=ret
			return ret
	if cnt%2==0:
		cnt+=1
		ret=max( func(x,y-1,cnt)+A[y] , func(x+1,y,cnt)+A[x]  )
	else:
		cnt+=1
		ret=min( func(x,y-1,cnt)-A[y] ,func(x+1,y ,cnt)-A[x] )

	dp[x][y]=ret
	return ret

func(0,N-1,0)

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


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

N=eval(input())
A=list(map(int, sys.stdin.readline().split()))

dp=[ [ None for i in range(N) ]  for j in range(N) ]


for i in range(N-1,-1,-1):
	if N%2==0:
		dp[i][i]=A[i]*-1
	else:
		dp[i][i]=A[i]


for i in range(N-2,-1,-1):
	for j in range(i+1,N):
		t=N-(j-i+1)	#残りの要素数
		if t%2==0:
			if dp[i][j] is None : dp[i][j]=float("-inf")
			dp[i][j]=max(dp[i][j] , dp[i][j-1]+A[j])
			dp[i][j]=max(dp[i][j] , dp[i+1][j]+A[i])
		else:
			if dp[i][j] is None : dp[i][j]=float("inf")
			dp[i][j]=min(dp[i][j] , dp[i][j-1]-A[j])
			dp[i][j]=min(dp[i][j] , dp[i+1][j]-A[i])

print(dp[0][N-1])
# Original solution
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()

    t = [[0]*n for _ in range(n)]
    for i in range(n):
        t[i][i] = a[i]

    for s in range(1,n):
        for i in range(n-s):
            j = i + s
            r = a[j] - t[i][j-1]
            u = a[i] - t[i+1][j]
            if r < u:
                r = u
            t[i][j] = r

    return t[0][-1]


print(main())


# Optimized solution
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()

    t = [[0]*n for _ in range(n)]
    for i in range(n):
        t[i][i] = a[i]

    for i in range(n-2,-1,-1):
        z = t[i]
        y = t[i+1]
        for j in range(i+1,n):
            r = a[j] - z[j-1]
            u = a[i] - y[j]
            if r < u:
                r = u
            z[j] = r

    return t[0][-1]


print(main())
# Original solution
import sys
sys.setrecursionlimit(10**7)

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

dp = [[None] * len(a) for _ in a]


def solve(i, j):
    if dp[i][j]:
        return dp[i][j]

    if i == j:
        dp[i][j] = a[i]
        return dp[i][j]

    dp[i][j] = max(a[j] - solve(i, j-1), a[i] - solve(i+1, j))
    return dp[i][j]


print((solve(0, len(a) - 1)))


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

dp = [[None] * len(a) for _ in a]

for i in range(len(a)-1, -1, -1):
    for j in range(i, len(a)):
        if i == j:
            dp[i][j] = a[i]
            continue

        dp[i][j] = max(a[j] - dp[i][j-1], a[i] - dp[i+1][j])

print((dp[0][len(a) - 1]))
# Original solution
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 9)

def main():
    N = int(eval(input()))
    a = list(map(int,input().split()))
    memo = [[-1 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        memo[i][i] = a[i]
    
    def point(x,y):
        if memo[x][y] != -1:
            return memo[x][y]
        else:
            ret = max(a[x]-point(x+1,y),a[y]-point(x,y-1))
            memo[x][y] = ret
            return ret
            
    point(0,N-1)
    print((memo[0][N-1]))
   
if __name__ == "__main__":
    main()


# Optimized solution
import sys
input = sys.stdin.buffer.readline

def main():
    N = int(eval(input()))
    a = list(map(int,input().split()))
    dp = [[-1 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        dp[i][i] = a[i]
    
    for i in range(N-1,-1,-1):
        for j in range(i,N):
            if dp[i][j] != -1:
                continue
            dp[i][j] = max(a[i]-dp[i+1][j],a[j]-dp[i][j-1])
            
    print((dp[0][-1]))
   
if __name__ == "__main__":
    main()
# Original solution
import sys
sys.setrecursionlimit(10**8)
n,*a=list(map(int,open(0).read().split()))
dp=[[0]*(n+1) for _ in range(n+1)]
def dfs(l,r):
	if l+r==n:return 0
	if dp[l][r]:return dp[l][r]
	dp[l][r]=max(a[l]-dfs(l+1,r),a[n-1-r]-dfs(l,r+1))
	return dp[l][r]
print((dfs(0,0)))

# Optimized solution
n,*a=list(map(int,open(0).read().split()))
dp=[[0]*(n+1) for _ in range(n+1)]
for l in range(n)[::-1]:
	for r in range(n)[::-1]:
		if l+r<=n-1:
			dp[l][r]=max(a[l]-dp[l+1][r],a[n-1-r]-dp[l][r+1])
print((dp[0][0]))
# Original solution
import sys
sys.setrecursionlimit(10**8)
def calc(N,i,j):
  if dp[i][j]<float('inf'):
    return dp[i][j]
  if (N-(j-i+1))%2==0:
    if i==j:
      dp[i][j] = A[i]
    else:
      dp[i][j] = max(calc(N,i,j-1)+A[j],calc(N,i+1,j)+A[i])
  else:
    if i==j:
      dp[i][j] = -A[i]
    else:
      dp[i][j] = min(calc(N,i,j-1)-A[j],calc(N,i+1,j)-A[i])
  return dp[i][j]

N = int(eval(input()))
A = list(map(int, input().split()))
dp = [[float('inf')]*N for _ in range(N)]
ans = calc(N,0,N-1)
print(ans)

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
dp = [[float('inf')]*N for _ in range(N)]
for i in range(N):
  if (N-1)%2==0:
    dp[i][i] = A[i]
  else:
    dp[i][i] = -A[i]
for k in range(1,N):
  for i in range(N):
    j = i+k
    if j>N-1:
      break
    if (N-(k+1))%2==0:
      dp[i][j] = max(dp[i][j-1]+A[j],dp[i+1][j]+A[i])
    else:
      dp[i][j] = min(dp[i][j-1]-A[j],dp[i+1][j]-A[i])
ans = dp[0][N-1]
print(ans)
# Original solution
import sys
input = sys.stdin.readline

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

SCORE=[[None for i in range(N+1)] for j in range(N+1)]

def score(i,j,k,l):#A[i:j)が残っているときのscore,1:Xの手番,-1:Yの手番
    #print(i,j,k,l)
    
    if SCORE[i][j]!=None:
        return SCORE[i][j]+k
    if i==j:
        SCORE[i][j]=0
        return k

        

    if l==1:
        SCORE[i][j]=max(score(i+1,j,k+A[i],-l),score(i,j-1,k+A[j-1],-l))-k
        return SCORE[i][j]+k
    if l==-1:
        SCORE[i][j]=min(score(i+1,j,k-A[i],-l),score(i,j-1,k-A[j-1],-l))-k
        return SCORE[i][j]+k



hand=N%2
for i in range(N+1):
    for j in range(N-i+1):
        score(j,j+i,0,(-1)**(j+j+i+hand))

print((SCORE[0][N]))

# Optimized solution
import sys
input = sys.stdin.readline

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

SCORE=[[None for i in range(N+1)] for j in range(N+1)]

def score(i,j,k,l):#A[i:j)が残っているときのscore,1:Xの手番,-1:Yの手番

    if i==j:
        SCORE[i][j]=0
        return
        
    if SCORE[i][j]!=None:
        return SCORE[i][j]+k

    if l==1:
        SCORE[i][j]=max(SCORE[i+1][j]+A[i],SCORE[i][j-1]+A[j-1])-k

    else:
        SCORE[i][j]=min(SCORE[i+1][j]-A[i],SCORE[i][j-1]-A[j-1])-k



hand=N%2
for i in range(N+1):
    for j in range(N-i+1):
        score(j,j+i,0,(-1)**(j+j+i+hand))

print((SCORE[0][N]))
# Original solution
import sys
sys.setrecursionlimit(10**7)
n=int(eval(input()))
a=list(map(int,input().split()))
d={}
def k(a):
      return ','.join(map(str,a))
def dp(a):
      ka=k(a)
      if ka in d:
            return [d[ka][0],d[ka][1]]
      if len(a)==1:
            d[ka]=[a[0],[]]
            return a[0],[]
      elif len(a)==2:
            d[ka]=[max(a),[min(a)]]
            return max(a),[min(a)]
      else:
            if a[0]-dp(a[1:])[0]>a[-1]-dp(a[:-1])[0]:
                  d[ka]=[a[0],a[1:]]
                  return a[0],a[1:]
            else:
                  d[ka]=[a[-1],a[:-1]]
                  return a[-1],a[:-1]
x,y=0,0
while a!=[]:
      x_,a=dp(a)
      x+=x_
      if a==[]:
            break
      y_,a=dp(a)
      y+=y_
print((x-y))


# Optimized solution
n=int(eval(input()))
a=list(map(int,input().split()))
dp=[[0]*n for _ in range(n)]
# dp[i][j]:i<=j,i番目からj番目までの数列(j-i+1個)を前にした時、ゲーム終了までに自分が取れる最大得点。i,j=0,..,n-1
sa=[0]
s=0
for ai in a:
      s+=ai
      sa.append(s)
for len in range(1,n+1):
      for l in range(n-len+1):
            r=l+len-1
            s=sa[r+1]-sa[l]
            dp[l][r]=max(s-dp[l][r-1],s-dp[l+1][r] if l+1<n else 0)
print((2*dp[0][-1]-sa[-1]))
# Original solution
from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(200000)

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

INF = -(10**13)

dp = [[INF] * (N + 1) for _ in range(N + 1)]


def play(start: 'int',
         end: 'int') -> 'int':  # return the maximum X for range[start,end)
    # if start + 1 == end:
    #     return start
    if dp[start][end] != INF:
        return dp[start][end]
    length = end - start
    if (N - length) & 1 == 0:  # taro plays
        if length == 1:
            dp[start][end] = a[start]
            return a[start]
        else:
            dp[start][end] = max(a[start] + play(start + 1, end),
                                 a[end - 1] + play(start, end - 1))
            return dp[start][end]
    else:  # jiro plays
        if length == 1:
            dp[start][end] = 0
            return 0
        else:
            dp[start][end] = min(play(start + 1, end), play(start, end - 1))
            return dp[start][end]


print((2 * play(0, N) - sum(a)))


# Optimized solution
from sys import stdin
input = stdin.readline

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

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

for i in range(N):
    dp[i][i + 1] = a[i] if N & 1 == 1 else -a[i]

for j in range(2, N + 1):
    for i in range(0, N + 1 - j):
        # j is the length of the interval + 1
        if (N - j) & 1 == 0:
            dp[i][i + j] = max(a[i] + dp[i + 1][i + j],
                               a[i + j - 1] + dp[i][i + j - 1])
        else:
            dp[i][i + j] = min(dp[i + 1][i + j] - a[i],
                               dp[i][i + j - 1] - a[i + j - 1])

print((dp[0][N]))
# Original solution
import sys


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return list([int(x) for x in read_line().split(' ')])[:n]


def read_float(n):
    return list([float(x) for x in read_line().split(' ')])[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    n = len(a)
    dp = [[None for x in range(n)] for y in range(n)]
    recursive_call(dp, a, len(a), 0, n - 1)
    return dp[0][n - 1]


def recursive_call(dp, a, n, l, r):
    if dp[l][r] is not None:
        return dp[l][r]
    if l == r:
        dp[l][r] = a[l]
        return dp[l][r]
    dp[l][r] = max(a[l] - recursive_call(dp, a, n, l + 1, r), a[r] - recursive_call(dp, a, n, l, r - 1))
    return dp[l][r]


def write(result):
    print(result)


if __name__ == '__main__':
    sys.setrecursionlimit(10000)
    solve()

# Optimized solution
def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return list(map(int, read_line().split(' ')))[:n]


def read_float(n):
    return list(map(float, read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    n = len(a)
    dp = [[None for x in range(n)] for y in range(n)]
    for i in range(len(dp)):
        dp[i][i] = a[i]
    for l in range(n - 2, -1, -1):
        for r in range(l + 1, n):
            dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1])
    return dp[0][n - 1]


def write(result):
    print(result)


if __name__ == '__main__':
    solve()
# Original solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from itertools import accumulate

n = int(eval(input()))
A = list(map(int, input().split()))
L = [0] + list(accumulate(A))
dp = [[-1]*(n+1) for i in range(n+1)]
def dfs(i, j):
  if dp[i][j] != -1:
    return dp[i][j]
  if i == j:
    dp[i][j] = 0
    return 0
  res = max(A[i] + L[j] - L[i+1] - dfs(i+1, j), A[j-1] + L[j-1] - L[i] - dfs(i, j-1))
  dp[i][j] = res
  return res
dfs(0, n)
ans = 2*dp[0][n] - L[n]
print(ans)

# Optimized solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from itertools import accumulate

n = int(eval(input()))
A = list(map(int, input().split()))
L = [0] + list(accumulate(A))
dp = [[0]*(n+1) for i in range(n+1)]
for d in range(1, n+1):
  for i in range(n+1-d):
    dp[i][i+d] = max(A[i] + L[i+d] - L[i+1] - dp[i+1][i+d], A[i+d-1] + L[i+d-1] - L[i] - dp[i][i+d-1])
ans = 2*dp[0][n] - L[n]
print(ans)
# Original solution
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(10**9)
#import
#import math
#import numpy as np
N = int(eval(input()))
A = list(map(int, input().split()))

dp = [[-1] * (N + 1) for _ in range(N + 1)]

# 半開区間A[r,l)における最大スコア
def calc(r, l):
    if dp[r][l] != -1:
        return dp[r][l]

    if l - r == 1:
        dp[r][l] = A[r]
        return dp[r][l]

    elif l - r == 2:
        dp[r][l] = max(A[r], A[r + 1]) - min(A[r], A[r + 1])
        return dp[r][l]

    res = max(A[r] - calc(r + 1, l), A[l - 1] - calc(r, l - 1))
    dp[r][l] = res
    return res

ans = calc(0, N)

print(ans)

# Optimized solution
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(10**9)
#import
#import math
#import numpy as np
N = int(eval(input()))
A = list(map(int, input().split()))

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


for w in range(1, N + 1):
    for l in range(N - w + 1):
        r = w + l
        dp[l][r] = A[l] - dp[l + 1][r]
        if r > 0:
            dp[l][r] = max(dp[l][r], A[r - 1] - dp[l][r - 1])

print((dp[0][N]))
# Original solution
N = int(eval(input()))
a = list(map(int, input().split()))
# dp[x][y][Person]:= 左端がx 番目,右端がy 番目の時の,この時動かすのがPersonの時の X - Y の値(0<=x<=Y<N)
dp = [[[0, 0] for j in range(N)] for i in range(N)]
for i in range(N):
    dp[i][i][0] = a[i]
    dp[i][i][1] = -a[i]

for i in range(1, N+1):
    # y-x = i  thus y = x+i  0<=x<N and 0<=x+i<N thus 0<=x <N-i
    for x in range(N-i):
        dp[x][x+i][0] = max(a[x]+dp[x+1][x+i][1], a[x+i]+dp[x][x+i-1][1])
        dp[x][x+i][1] = min(dp[x+1][x+i][0]-a[x], dp[x][x+i-1][0]-a[x+i])

ans = dp[0][N-1][0]
print(ans)

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

for i in range(1, N+1):
    for x in range(N-i):
        dp[x][x+i] = max(a[x]+dp[x+1][x+i+N], a[x+i]+dp[x][x+i-1+N])
        dp[x][x+i+N] = min(dp[x+1][x+i]-a[x], dp[x][x+i-1]-a[x+i])
ans = dp[0][N-1]
print(ans)
# Original solution
import sys
sys.setrecursionlimit(5000)
def max(a,b):
    if a >= b:
        return a
    return b
def min(a,b):
    if a <= b:
        return a
    return b

def main():

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

    dp = [[-1]*(n+1) for i in range(n)]
    def rec(i=0, j=n):
        if i == j:
            return 0
        if dp[i][j] != -1:
            return dp[i][j]
        # 太郎
        if (n - (j-i))%2==0:
            dp[i][j] = max(a[i] + rec(i+1,j), a[j-1] +rec(i,j-1))
        else:
            dp[i][j] = min(-a[i] + rec(i+1,j), -a[j-1] +rec(i,j-1))
        return dp[i][j]
    print((rec()))

main()

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

dp = [[0]*(n+1) for i in range(n+1)]
for l in range(1,n+1):
    for i in range(n+1-l):
        j = i+l
        if (n-l)%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])
print((dp[0][-1]))
# Original solution
#EDPC L
import sys
sys.setrecursionlimit(10**5)


def main():

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

    #dp[l][r]:=区間[l,r]が残っている時の(直後の人の最終的な得点-そうじゃない方の最終的な得点）

    dp=[[-1]*N for _ in range(N)]

    def rec(l,r):
        if dp[l][r]!=-1:
            return dp[l][r]
        
        if l==r:
            dp[l][r]=a[l]
            return dp[l][r]
        
        dp[l][r]=max(a[l]-rec(l+1,r),a[r]-rec(l,r-1))

        return dp[l][r]


    print((rec(0,N-1)))
main()

# Optimized solution
#EDPC L メモ化再帰じゃTLEで通らないのでやり直し

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

#dp[l][r]:=区間[l,r]が残っている時の(直後の人の最終的な得点-そうじゃない方の最終的な得点）

dp=[[-1]*N for _ in range(N)]

for k in range(N):
    dp[k][k]=a[k]

for r in range(1,N):
    for l in reversed(list(range(r))):
        dp[l][r]=max(a[l]-dp[l+1][r],a[r]-dp[l][r-1])

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

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

for length in range(1, n + 1):
    for i in range(n - length + 1):
        j = i + length

        if ((n - length) % 2 == 0):
            dp[i][j] = max(dp[i+1][j] + arr[i], dp[i][j-1] + arr[j-1])
        else:
            dp[i][j] = min(dp[i+1][j] - arr[i], dp[i][j-1] - arr[j-1])


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


# 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 ** 6)


def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    c = [[None] * N for _ in range(N)]
    for r in reversed(list(range(N))):
        c[r][r] = A[r]
        for l in range(r + 1, N):
            c[r][l] = max(-c[r + 1][l] + A[r], -c[r][l - 1] + A[l])
    
    print((c[0][N - 1]))


main()


# Optimized solution
def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    c = [0] * N
    for r in reversed(list(range(N))):
        ar = A[r]
        c[r] = t = ar
        for l in range(r + 1, N):
            c[l] = t = max(ar - c[l], A[l] - t)
    
    print((c[-1]))


main()
# Original solution
N = int(eval(input()))
a = [int(c) for c in input().split()]

dp = [[-1] * N for _ in range(N)]
for i in range(N):
    for L in range(N):
        for R in range(L, N):
            if L == R:
                dp[L][R] = a[L]
            else:
                dp[L][R] = max(a[L] - dp[L+1][R], a[R] - dp[L][R-1])


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


# Optimized solution
N = int(eval(input()))
a = [int(c) for c in input().split()]

dp = [[-1] * N for _ in range(N)]
for L in range(N, -1, -1):
    for R in range(L, N):
        if L == R:
            dp[L][R] = a[L]
        else:
            dp[L][R] = max(a[L] - dp[L+1][R], a[R] - dp[L][R-1])


print((dp[0][N-1]))
# Original solution
import sys
input = sys.stdin.readline

def func():
    N = int(eval(input()))
    A = [int(i) for i in input().split()]

    dp = [[0] * (N+1) for i in range(N+1)]
    if (N - 1) % 2 == 0:
        fl = 1
    else:
        fl = -1
    for i in range(N):
        dp[i][i+1] = fl * A[i]

    for s in range(2, N+1):
        for l in range(N-s+1):
            r = l + s
            if (N - s) % 2 == 0:
                dp[l][r] = max(dp[l+1][r]+A[l], dp[l][r-1]+A[r-1])
                continue
            dp[l][r] = min(dp[l+1][r]-A[l], dp[l][r-1]-A[r-1])
                
    return dp[0][N]

print((func()))

# Optimized solution
import sys
input = sys.stdin.readline

def func():
    N = int(eval(input()))
    A = [int(i) for i in input().split()]

    dp = [[0] * (N+1) for i in range(N+1)]
    for i in range(N):
        dp[i][i+1] = A[i]

    for s in range(2, N+1):
        for l in range(N-s+1):
            r = l + s
            dp[l][r] = max(A[l]-dp[l+1][r], A[r-1]-dp[l][r-1])
                            
    return dp[0][N]

print((func()))
# Original solution
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

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

dp_memo = [[float("inf")]*(N+1) for _ in range(N+1)]
for i in range(N+1):
    dp_memo[i][i] = 0

def dp(i,j):
    if dp_memo[i][j] < float("inf"):
        return dp_memo[i][j]
    elif (j-i)%2 == N%2: # 先手番
        tmp = max(a[i] + dp(i+1, j), a[j-1] + dp(i,j-1))
        dp_memo[i][j] = tmp
        return tmp
    else: # 後手番
        tmp = min(-a[i] + dp(i+1, j), -a[j-1] + dp(i,j-1))
        dp_memo[i][j] = tmp
        return tmp

print((dp(0, N)))

# Optimized solution
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

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

dp = [[float("inf")]*(N+1) for _ in range(N+1)]

for shift_i in range(N+1):
    for i in range(N+1):
        if i+shift_i >= N+1:
            continue
        if shift_i == 0:
            dp[i][i] = 0
        elif ((i+shift_i)-i)%2 == N%2: # 先手番
            dp[i][(i+shift_i)] = max(a[i] + dp[i+1][(i+shift_i)], a[(i+shift_i)-1] + dp[i][(i+shift_i)-1])
        else:
            dp[i][(i+shift_i)] = min(-a[i] + dp[i+1][(i+shift_i)], -a[(i+shift_i)-1] + dp[i][(i+shift_i)-1])

print((dp[0][N]))
# Original solution
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

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

dp = [[float("inf")]*(N+1) for _ in range(N+1)]

for shift_i in range(N+1):
    for i in range(N+1):
        if i+shift_i >= N+1:
            continue
        if shift_i == 0:
            dp[i][i] = 0
        elif ((i+shift_i)-i)%2 == N%2: # 先手番
            dp[i][(i+shift_i)] = max(a[i] + dp[i+1][(i+shift_i)], a[(i+shift_i)-1] + dp[i][(i+shift_i)-1])
        else:
            dp[i][(i+shift_i)] = min(-a[i] + dp[i+1][(i+shift_i)], -a[(i+shift_i)-1] + dp[i][(i+shift_i)-1])

print((dp[0][N]))

# Optimized solution
import sys
input = sys.stdin.buffer.readline

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

# dp[i][j] 区間a[i,j)だけ残った時点で互いの点数を一旦0とし、ゲームを最後まで続けた場合のX-Yの値
dp = [[0]*(N+1) for _ in range(N+1)]

# こちらもメモ化再帰ではpypy3でも間に合わない
# j==i+1, i+2, ...とループしてdpテーブルの上三角部分を対角線と平行に埋めていく。jをshift_iと書き換えてループ
for shift_i in range(1, N+1):
    for i in range(N+1):
        if i+shift_i >= N+1:
            continue
        elif ((i+shift_i)-i)%2 == N%2: # 先手番
            dp[i][(i+shift_i)] = max(a[i] + dp[i+1][(i+shift_i)], a[(i+shift_i)-1] + dp[i][(i+shift_i)-1])
        else:
            dp[i][(i+shift_i)] = min(-a[i] + dp[i+1][(i+shift_i)], -a[(i+shift_i)-1] + dp[i][(i+shift_i)-1])

print((dp[0][N]))