[USACO09NOV] A Coin Game S
题目背景
[原英文题面见链接](https://www.luogu.com.cn/paste/9orda6gz)。
题目描述
小 A 和小 B 在玩游戏。
初始时,有 $n$ 个硬币被摆成了一行,从左至右第 $i$ 个硬币的价值为 $c_i$。
游戏的规则是,两人交替从这堆硬币的**左侧**连续取出若干硬币,然后将取出的硬币的价值累加至自己获得的累计价值中。若对方上次操作取出了 $k$ 个硬币,那么本次自己最多取出 $k \times 2$ 个硬币。当没有硬币可取时,游戏结束。
游戏开始时,由小 A 先动手取硬币,最多取出 $2$ 个硬币。
请求出当双方都尽可能使自己的累计价值最大的情况下,小 A 能获得的累计价值最大是多少。
输入输出格式
输入格式
输入的第一行是一个整数 $n$,代表硬币的个数。
第 $2$ 到第 $(n + 1)$ 行,每行一个整数,第 $(i + 1)$ 行的整数代表第 $i$ 个硬币的价值 $c_i$。
输出格式
输出一行一个整数,代表小 A 能获得的最大累计价值。
输入输出样例
输入样例 #1
5
1
3
1
7
2
输出样例 #1
9
说明
#### 输出输出样例 $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**。