## 题目背景
[原英文题面见链接](https://www.luogu.com.cn/paste/9orda6gz)。
```markdown
[原英文题面见链接](https://www.luogu.com.cn/paste/9orda6gz)。
```
## 题目描述
小 A 和小 B 在玩游戏。
初始时，有 $n$ 个硬币被摆成了一行，从左至右第 $i$ 个硬币的价值为 $c_i$。
游戏的规则是，两人交替从这堆硬币的**左侧**连续取出若干硬币，然后将取出的硬币的价值累加至自己获得的累计价值中。若对方上次操作取出了 $k$ 个硬币，那么本次自己最多取出 $k \times 2$ 个硬币。当没有硬币可取时，游戏结束。
游戏开始时，由小 A 先动手取硬币，最多取出 $2$ 个硬币。
请求出当双方都尽可能使自己的累计价值最大的情况下，小 A 能获得的累计价值最大是多少。
```markdown
小 A 和小 B 在玩游戏。
初始时，有 $n$ 个硬币被摆成了一行，从左至右第 $i$ 个硬币的价值为 $c_i$。
游戏的规则是，两人交替从这堆硬币的**左侧**连续取出若干硬币，然后将取出的硬币的价值累加至自己获得的累计价值中。若对方上次操作取出了 $k$ 个硬币，那么本次自己最多取出 $k \times 2$ 个硬币。当没有硬币可取时，游戏结束。
游戏开始时，由小 A 先动手取硬币，最多取出 $2$ 个硬币。
请求出当双方都尽可能使自己的累计价值最大的情况下，小 A 能获得的累计价值最大是多少。
```
## 输入格式
输入的第一行是一个整数 $n$，代表硬币的个数。
第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数代表第 $i$ 个硬币的价值 $c_i$。
```markdown
输入的第一行是一个整数 $n$，代表硬币的个数。
第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数代表第 $i$ 个硬币的价值 $c_i$。
```
## 输出格式
输出一行一个整数，代表小 A 能获得的最大累计价值。
```markdown
输出一行一个整数，代表小 A 能获得的最大累计价值。
```
## 说明/提示
#### 输出输出样例 $1$ 解释
初始时，硬币序列为 $\{1,~3,~1,~7,~2\}$。
由小 A 先操作，他取出了一个硬币，硬币序列变为 $\{3,~1,~7,~2\}$，小 A 的累计价值为 $1$。
再由小 B 操作，由于小 A 上回合取出了 $1$ 个硬币，所以他本回合可以取出至多 $1 \times 2 = 2$ 个硬币。他取出了一个硬币，硬币序列变为 $\{1,~7,~2\}$，小 B 的累计价值为 $3$。
再由小 A 操作，由于上回合小 B 取出了 $1$ 个硬币，所以他本回合可以取出至多 $1 \times 2 = 2$ 个硬币。他取出了两个硬币，硬币序列变为 $\{2\}$，小 A 的累计价值为 $1 + 1 + 7 = 9$。
再由小 B 操作，由于上回合小 A 取出了 $2$ 个硬币，所以他本回合可以取出至多 $2 \times 2 = 4$ 个硬币。但是只剩下了 $1$ 个硬币，因此他只能取出一个硬币，硬币序列变为空，小 B 的累计价值为 $3 + 2 = 5$，游戏结束。
#### 数据范围与约定
对于全部的测试点，保证 $5 \leq n \leq 2 \times 10^3$，$1 \leq c_i \leq 10^5$。
**提示：请注意本题的空间限制为 $20$ Mib**。
```markdown
#### 输出输出样例 $1$ 解释
初始时，硬币序列为 $\{1,~3,~1,~7,~2\}$。
由小 A 先操作，他取出了一个硬币，硬币序列变为 $\{3,~1,~7,~2\}$，小 A 的累计价值为 $1$。
再由小 B 操作，由于小 A 上回合取出了 $1$ 个硬币，所以他本回合可以取出至多 $1 \times 2 = 2$ 个硬币。他取出了一个硬币，硬币序列变为 $\{1,~7,~2\}$，小 B 的累计价值为 $3$。
再由小 A 操作，由于上回合小 B 取出了 $1$ 个硬币，所以他本回合可以取出至多 $1 \times 2 = 2$ 个硬币。他取出了两个硬币，硬币序列变为 $\{2\}$，小 A 的累计价值为 $1 + 1 + 7 = 9$。
再由小 B 操作，由于上回合小 A 取出了 $2$ 个硬币，所以他本回合可以取出至多 $2 \times 2 = 4$ 个硬币。但是只剩下了 $1$ 个硬币，因此他只能取出一个硬币，硬币序列变为空，小 B 的累计价值为 $3 + 2 = 5$，游戏结束。
#### 数据范围与约定
对于全部的测试点，保证 $5 \leq n \leq 2 \times 10^3$，$1 \leq c_i \leq 10^5$。
**提示：请注意本题的空间限制为 $20$ Mib**。
```
by 一扶苏一 @ 2020-01-15 18:39:38
另外根据英文题面，本题的空间限制应该是20M，这样会卡掉不顺手维护最大值的代码。
by 一扶苏一 @ 2020-01-15 18:40:33
@[mrsrz](/user/6813)
by 一扶苏一 @ 2020-01-15 18:40:39
@[一扶苏一](/user/65363) 感谢您的贡献
by mrsrz @ 2020-01-15 18:42:55