CF729F.Financiers Game

This problem has unusual memory constraint.

At evening, Igor and Zhenya the financiers became boring, so they decided to play a game. They prepared n papers with the income of some company for some time periods. Note that the income can be positive, zero or negative.

Igor and Zhenya placed the papers in a row and decided to take turns making moves. Igor will take the papers from the left side, Zhenya will take the papers from the right side. Igor goes first and takes 1 or 2 (on his choice) papers from the left. Then, on each turn a player can take k or k + 1 papers from his side if the opponent took exactly k papers in the previous turn. Players can't skip moves. The game ends when there are no papers left, or when some of the players can't make a move.

Your task is to determine the difference between the sum of incomes on the papers Igor took and the sum of incomes on the papers Zhenya took, assuming both players play optimally. Igor wants to maximize the difference, Zhenya wants to minimize it.

本题具有特殊的内存限制。

傍晚时分，金融家伊戈尔和热尼亚感到无聊，于是决定玩一个游戏。他们准备了 $n$ 张纸，每张纸上写有某公司在某段时间内的收入。注意：收入可以为正数、零或负数。

伊戈尔和热尼亚将这些纸张排成一排，并决定轮流进行操作。伊戈尔从左侧取纸，热尼亚从右侧取纸。伊戈尔先手，他可选择从左侧取 $1$ 张或 $2$ 张纸。此后，在每一轮中，若对手上一轮恰好取了 $k$ 张纸，则当前玩家必须从自己一侧取 $k$ 张或 $k+1$ 张纸。玩家不能跳过自己的回合。当所有纸张均被取完，或某位玩家无法进行合法操作时，游戏结束。

你的任务是：在双方均采取最优策略的前提下，计算伊戈尔所取纸张上的收入总和与热尼亚所取纸张上的收入总和之差。其中，伊戈尔希望最大化该差值，而热尼亚希望最小化该差值。

The first line contains single positive integer n (1 ≤ n ≤ 4000) — the number of papers.

The second line contains n integers _a_1, _a_2, ..., a__n ( - 105 ≤ a__i ≤ 105), where a__i is the income on the i-th paper from the left.

第一行包含一个正整数 $n$（$1 \leq n \leq 4000$）——论文的数量。

第二行包含 $n$ 个整数 $a_1,\,a_2,\,...,\,a_n$（$-10^5 \leq a_i \leq 10^5$），其中 $a_i$ 表示从左往右数第 $i$ 篇论文的收入。

Print the difference between the sum of incomes on the papers Igor took and the sum of incomes on the papers Zhenya took, assuming both players play optimally. Igor wants to maximize the difference, Zhenya wants to minimize it.

输出伊戈尔所选论文的收入总和与珍雅所选论文的收入总和之差，假设双方均采取最优策略。伊戈尔希望最大化该差值，而珍雅希望最小化该差值。

In the first example it's profitable for Igor to take two papers from the left to have the sum of the incomes equal to 4. Then Zhenya wouldn't be able to make a move since there would be only one paper, and he would be able to take only 2 or 3..

在第一个例子中，Igor 从左侧取走两张纸片是划算的，这样他的收入总和为 4。随后 Zhenya 将无法进行操作，因为此时只剩一张纸片，而他每次只能取走 2 张或 3 张。