{"raw_statement":[{"iden":"problem statement","content":"Taro and Jiro will play the following game against each other.\nInitially, 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:\n\n*   Remove the element at the beginning or the end of $a$. The player earns $x$ points, where $x$ is the removed element.\n\nLet $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$.\nAssuming that the two players play optimally, find the resulting value of $X - Y$."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $1 \\leq N \\leq 3000$\n*   $1 \\leq a_i \\leq 10^9$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$a_1$ $a_2$ $\\ldots$ $a_N$"},{"iden":"sample input 1","content":"4\n10 80 90 30"},{"iden":"sample output 1","content":"10\n\nThe game proceeds as follows when the two players play optimally (the element being removed is written bold):\n\n*   Taro: (10, 80, 90, **30**) → (10, 80, 90)\n*   Jiro: (10, 80, **90**) → (10, 80)\n*   Taro: (10, **80**) → (10)\n*   Jiro: (**10**) → ()\n\nHere, $X = 30 + 80 = 110$ and $Y = 90 + 10 = 100$."},{"iden":"sample input 2","content":"3\n10 100 10"},{"iden":"sample output 2","content":"\\-80\n\nThe game proceeds, for example, as follows when the two players play optimally:\n\n*   Taro: (**10**, 100, 10) → (100, 10)\n*   Jiro: (**100**, 10) → (10)\n*   Taro: (**10**) → ()\n\nHere, $X = 10 + 10 = 20$ and $Y = 100$."},{"iden":"sample input 3","content":"1\n10"},{"iden":"sample output 3","content":"10"},{"iden":"sample input 4","content":"10\n1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1"},{"iden":"sample output 4","content":"4999999995\n\nThe answer may not fit into a 32-bit integer type."},{"iden":"sample input 5","content":"6\n4 2 9 7 1 5"},{"iden":"sample output 5","content":"2\n\nThe game proceeds, for example, as follows when the two players play optimally:\n\n*   Taro: (4, 2, 9, 7, 1, **5**) → (4, 2, 9, 7, 1)\n*   Jiro: (**4**, 2, 9, 7, 1) → (2, 9, 7, 1)\n*   Taro: (2, 9, 7, **1**) → (2, 9, 7)\n*   Jiro: (2, 9, **7**) → (2, 9)\n*   Taro: (2, **9**) → (2)\n*   Jiro: (**2**) → ()\n\nHere, $X = 5 + 1 + 9 = 15$ and $Y = 4 + 7 + 2 = 13$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}