题目背景

原英文题面见链接。

题目描述

小 A 和小 B 在玩游戏。

初始时，有 $n$ 个硬币被摆成了一行，从左至右第 $i$ 个硬币的价值为 $c_i$。

游戏的规则是，两人交替从这堆硬币的左侧连续取出若干硬币，然后将取出的硬币的价值累加至自己获得的累计价值中。若对方上次操作取出了 $k$ 个硬币，那么本次自己最多取出 $k \times 2$ 个硬币。当没有硬币可取时，游戏结束。

游戏开始时，由小 A 先动手取硬币，最多取出 $2$ 个硬币。

请求出当双方都尽可能使自己的累计价值最大的情况下，小 A 能获得的累计价值最大是多少。

输入格式

输入的第一行是一个整数 $n$，代表硬币的个数。

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数代表第 $i$ 个硬币的价值 $c_i$。

输出格式

输出一行一个整数，代表小 A 能获得的最大累计价值。

5 
1 
3 
1 
7 
2 

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。