问题描述

高桥将按顺序遇到 $N$ 个怪物。第 $i(1\leq i\leq N)$ 个怪物具有 $A_i$ 的强度。

对于每一个怪物，他可以选择放它走或者打败它。

每个行动奖励他的经验值如下:

• 如果他放走了怪物，他将获得 0 点经验值。
• 如果他打败了一个力量为 $X$ 的怪物，他将获得 $X$ 点经验值。
• 如果这是第偶数个（第 2，第 4，..）被击败的怪物，他将获得额外的 $X$ 点经验值。

找出他可以从 $N$ 个怪物中获得的最大总经验值。

数据规模

$1\leq N\leq 2×10^5$

$1\leq A_i\leq 10^9$

所有输入值都是整数。

输入

输入来自标准输入，格式如下:

$N$

$A_1\ A_2\ \ldots\ A_N$

输出

打印他可以从 $N$ 个怪物中获得的最大总经验值。

5
1 5 3 2 7

28

如果高桥打败了第 1、第 2、第 3 和第 5 只怪物，并放走了第 4 只怪物，他获得的经验值如下:

• 击败一个力量为 $A_1=1$ 的怪物。他获得 1 点经验值。
• 击败一个力量为 $A_2=5$ 的怪物。他获得 5 点经验值。因为它是第二个被击败的怪物，他获得了额外的 5 点。
• 击败一个力量为 $A_3=3$ 的怪物。他获得 3 点经验值。
• 让第四个怪物走吧。高桥没有获得经验值。
• 用力量击败一个怪物，$A_5=7$。他获得 7 点经验值。因为这是第四个被击败的怪物，他获得了额外的 7 分。

因此，在这种情况下，他获得 $1+(5+5)+3+0+(7+7)=28$ 经验值。注意，即使他遇到了怪物，如果他让它走了，它也不算被打败。

无论他如何行动，他最多可以获得 28 点经验值，所以打印 28 点。顺便说一下，如果他在这种情况下击败所有怪物，他将获得 $1+(5+5)+3+(2+2)+7=25$ 点经验值。

2
1000000000 1000000000

3000000000

请注意，答案可能不适合 $32$ 位整数。