题目描述

小可和小达在游戏中探险，他们按顺序遇到了 $N$ 个宝箱，第 $i$ 个宝箱里装有 $A_i$ 枚金币。

对于每个宝箱，他们可以选择：

• 不打开：获得 $0$ 枚金币
• 打开：立即获得 $A_i$ 枚金币，并且如果这是他们打开的第 偶数个 宝箱（即第 $2$ 个、第 $4$ 个……），还会额外获得 $A_i$ 枚金币作为奖励！

小可想知道，通过合理地选择打开哪些宝箱，他们最多能获得多少枚金币？

输入格式

输入共两行：

第一行一个整数 $N$，表示宝箱的数量。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$，表示每个宝箱里的金币数量。

输出格式

输出一个整数，表示能获得的最大金币总数。

样例

5
1 5 3 2 7

28

2
1000000000 1000000000

3000000000

提示

样例解释

样例1：

打开第 $1$、$2$、$3$、$5$ 个宝箱，不打开第 $4$ 个宝箱：

• 打开第 $1$ 个宝箱（$A_1=1$）：获得 $1$ 枚金币（这是第 $1$ 次打开，无额外奖励）
• 打开第 $2$ 个宝箱（$A_2=5$）：获得 $5$ 枚金币，并且因为这是第 $2$ 次打开，额外奖励 $5$ 枚金币
• 打开第 $3$ 个宝箱（$A_3=3$）：获得 $3$ 枚金币
• 不打开第 $4$ 个宝箱：获得 $0$ 枚金币
• 打开第 $5$ 个宝箱（$A_5=7$）：获得 $7$ 枚金币，并且因为这是第 $4$ 次打开，额外奖励 $7$ 枚金币

总计：$1 + (5+5) + 3 + 0 + (7+7) = 28$ 枚金币

注意：如果打开所有宝箱，只能获得 $1 + (5+5) + 3 + (2+2) + 7 = 25$ 枚金币，不是最优的。

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• 输入的所有数均为整数