output_description: Print the resulting value of X - Y, assuming that the two players play
  optimally.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      a_1 a_2 \ldots a_N
attempt: import subprocess as sp
  import sys
  
  code = r"""
  n=int(input())
  a=[int(j) for j in input().split()]
  dp=[[0]*(n+1) for i in range(n+1)]
  
  for i in range(n)[::-1]:
      for j in range(i,n):
          if (n+i-j-1)%2==0:
              dp[i][j]=max(dp[i+1][j]+a[i],dp[i][j-1]+a[j])
          else:
              dp[i][j]=min(dp[i+1][j]-a[i],dp[i][j-1]-a[j])
  print(dp[0][n-1])
  
  """
  with open("A.py", "w") as f:
      f.write(code)
  sp.Popen(["pypy", "-std=pypy", "-O2", "A.py"]).communicate()
  sp.Popen(["./a.out"], stdin=sys.stdin, stdout=sys.stdout).communicate()
  
problem_description: Statement
  
  Taro and Jiro will play the following game against each other.
  
  Initially, they are given a sequence a = (a_1, a_2, \ldots, a_N). Until a
  becomes empty, the two players perform the following operation alternately,
  starting from Taro:
  
    * Remove the element at the beginning or the end of a. The player earns x points, where x is the removed element.
  
  Let X and Y be Taro's and Jiro's total score at the end of the game,
  respectively. Taro tries to maximize X - Y, while Jiro tries to minimize X -
  Y.
  
  Assuming that the two players play optimally, find the resulting value of X -
  Y.
samples: [{"input": "4\n    10 80 90 30", "output": "10\n    \n\nThe game proceeds as follows when the two players play optimally (the element\nbeing removed is written bold):\n\n  * Taro: (10, 80, 90, **30**) \u2192 (10, 80, 90)\n  * Jiro: (10, 80, **90**) \u2192 (10, 80)\n  * Taro: (10, **80**) \u2192 (10)\n  * Jiro: (**10**) \u2192 ()\n\nHere, X = 30 + 80 = 110 and Y = 90 + 10 = 100.\n\n* * *"}, {"input": "3\n    10 100 10", "output": "-80\n    \n\nThe game proceeds, for example, as follows when the two players play\noptimally:\n\n  * Taro: (**10** , 100, 10) \u2192 (100, 10)\n  * Jiro: (**100** , 10) \u2192 (10)\n  * Taro: (**10**) \u2192 ()\n\nHere, X = 10 + 10 = 20 and Y = 100.\n\n* * *"}, {"input": "1\n    10", "output": "10\n    \n\n* * *"}, {"input": "10\n    1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1", "output": "4999999995\n    \n\nThe answer may not fit into a 32-bit integer type.\n\n* * *"}, {"input": "6\n    4 2 9 7 1 5", "output": "2\n    \n\nThe game proceeds, for example, as follows when the two players play\noptimally:\n\n  * Taro: (4, 2, 9, 7, 1, **5**) \u2192 (4, 2, 9, 7, 1)\n  * Jiro: (**4** , 2, 9, 7, 1) \u2192 (2, 9, 7, 1)\n  * Taro: (2, 9, 7, **1**) \u2192 (2, 9, 7)\n  * Jiro: (2, 9, **7**) \u2192 (2, 9)\n  * Taro: (2, **9**) \u2192 (2)\n  * Jiro: (**2**) \u2192 ()\n\nHere, X = 5 + 1 + 9 = 15 and Y = 4 + 7 + 2 = 13."}]