题目描述

FJ的奶牛们很喜欢玩硬币游戏，所以FJ给她们发明了一个新的双人硬币游戏：xoinc。

一开始地上有一个由$N(5 \le N\le2000)$个硬币组成的栈，从栈顶数起的第$i$枚硬币有自己的价值$C_i(1\le C_i\le100000)$。

在游戏开始时，先手玩家可以从栈顶拿$1$或$2$枚硬币。如果先手玩家只拿走了$1$枚，那么后手玩家就在接下来拿走$1$或$2$枚；如果先手玩家拿走了$2$枚，那么后手玩家就在接下来拿走$1$到$4$枚。也就是说，除了第一回合，每一回合的玩家都必须拿走至少$1$枚，至多自己的对手在上回合拿走的数目的两倍的硬币数。当栈中的硬币全部被拿走，游戏结束。

在这之后，牛们可以拿她们拿到的硬币向FJ交♂易买东西，所以游戏目标自然是让自己拿到的硬币的价值尽量大。假设后手玩家采取了最好的决策，那么先手玩家能拿到的最大的硬币价值是多少？

输入格式

第一行一个整数$N$，接下来$N$行每行一个整数$C_i$。

输出格式

一行一个整数，双方都采取最佳策略时先手拿到的硬币价值。

样例不放了……

样例解释：

先手先拿走第一个硬币，价值为1，然后后手也拿走一个价值为3的硬币，先手再拿走两个硬币，价值为1和7，总价值为1+1+7=9。然后后手拿走剩下的一枚硬币。 致敬：x义x