{"problem":{"name":"Deque","description":{"content":"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 operat","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"dp_l"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq N \\leq 3000$\n*   $1 \\leq a_i \\leq 10^9$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_1$ $a_2$ $\\ldots$ $a_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"dp_l","tags":[],"sample_group":[["4\n10 80 90 30","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$."],["3\n10 100 10","\\-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$."],["1\n10","10"],["10\n1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1","4999999995\n\nThe answer may not fit into a 32-bit integer type."],["6\n4 2 9 7 1 5","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$."]],"created_at":"2026-03-03 11:01:14"}}