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: N=int(input())
  a = list(map(int, input().split()))
  
  dp=[[0 for i in range(N+1)] for j in range(N+1)]
  for i in range(1,N+1):
      dp[i][i]=a[i-1]
  for j in range(1,N+1):
      for i in reversed(range(1,N+1)):
          if i>j:
              continue
          if i==j:
              dp[i][j]=a[i-1]
          if i<j:
              dp[i][j]=max(a[i-1]-dp[i+1][j],a[j-1]-dp[i][j-1])
  print(dp[1][N]
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."}]