题目描述

农夫约翰的奶牛喜欢玩硬币游戏，因此他发明了一种称为"$\red{Xoinc}$"的两人硬币游戏。 初始时，一个有$\red{N(5 <= N <= 2,000)}$枚硬币的堆栈放在地上，从堆顶数起的第$\red{I}$枚硬币的币值为$\red{C_i (1 <= C_i <= 100,000)}$。

开始玩游戏时，第一个玩家可以从堆顶拿走一枚或两枚硬币。如果第一个玩家只拿走堆顶的一枚硬币，那么第二个玩家可以拿走随后的一枚或两枚硬币。如果第一个玩家拿走两枚硬币，则第二个玩家可以拿走$\red{1，}$$\red{2，}$$\red{3，}$或$\red{4}$枚硬币。在每一轮中，当前的玩家至少拿走一枚硬币，至多拿走对手上一次所拿硬币数量的两倍。当没有硬币可拿时，游戏结束。 两个玩家都希望拿到最多钱数的硬币。

请问，当游戏结束时，第一个玩家最多能拿多少钱呢？

输入格式

第$\red{1}$行：$\red{1}$个整数$\red{N}$

第$\red{2..N+1}$行：第$\red{i+1}$行包含$\red{1}$个整数$\red{C_i}$

输出格式

第$\red{1}$行：$\red{1}$个整数表示第$\red{1}$个玩家能拿走的最大钱数。

样例

输入样例

5
1
3
1
7
2

输出样例

9

提示

样例说明：第$\red{1}$个玩家先取走第$\red{1}$枚，第$\red{2}$个玩家取第$\red{2}$枚；第$\red{1}$个取走第$\red{3，}$$\red{4}$两枚，第$\red{2}$个玩家取走最后$\red{1}$枚。