3280 - 轮流取数2

小 A 和小 B 在玩游戏。

初始时,数组有 n 个数从左到右摆放,从左至右第 i 个数值为 c_i

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

游戏开始时,由小 A 先动手取数,最多取出 2 个数。

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

输入

输入的第一行是一个整数 n,代表数组的长度。

2 到第 (n + 1) 行,每行一个整数c_i ,表示数组每个数的值。

输出

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

样例

输入

5 
1 
3 
1 
7 
2

输出

9

提示

5 \leq n \leq 2 \times 10^31 \leq c_i \leq 10^5

来源

USACO

时间限制 1 秒
内存限制 32 MB
讨论 统计
上一题 下一题