103693: [Atcoder]ABC369 D - Bonus EXP

Problem Statement

Takahashi will encounter $N$ monsters in order. The $i$-th monster $(1\leq i\leq N)$ has a strength of $A_i$.

For each monster, he can choose to either let it go or defeat it.
Each action awards him experience points as follows:

• If he lets a monster go, he gains $0$ experience points.
• If he defeats a monster with strength $X$, he gains $X$ experience points.
  If it is an even-numbered defeated monster (2nd, 4th, ...), he gains an additional $X$ experience points.

Find the maximum total experience points he can gain from the $N$ monsters.

Constraints

• $1\leq N\leq 2\times 10^5$
• $1\leq A_i\leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

Output

Print the maximum total experience points he can gain from the $N$ monsters as an integer.

Sample Input 1

5
1 5 3 2 7

Sample Output 1

28

If Takahashi defeats the 1st, 2nd, 3rd, and 5th monsters, and lets the 4th monster go, he gains experience points as follows:

• Defeats a monster with strength $A_1=1$. He gains $1$ experience point.
• Defeats a monster with strength $A_2=5$. He gains $5$ experience points. As it is the 2nd defeated monster, he gains an additional $5$ points.
• Defeats a monster with strength $A_3=3$. He gains $3$ experience points.
• Lets the 4th monster go. Takahashi gains no experience points.
• Defeats a monster with strength $A_5=7$. He gains $7$ experience points. As it is the 4th defeated monster, he gains an additional $7$ points.

Therefore, in this case, he gains $1+(5+5)+3+0+(7+7)=28$ experience points.
Note that even if he encounters a monster, if he lets it go, it does not count as defeated.

He can gain at most $28$ experience points no matter how he acts, so print $28$.
As a side note, if he defeats all monsters in this case, he would gain $1+(5+5)+3+(2+2)+7=25$ experience points.

Sample Input 2

2
1000000000 1000000000

Sample Output 2

3000000000

Beware that the answer may not fit in a $32$-bit integer.

问题陈述

高桥将依次遭遇N个怪物。第i个怪物（1≤i≤N）的强度为A_i。

对于每个怪物，他可以选择放它走或者击败它。
每个行动都会给他奖励经验点数如下：

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

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

约束条件

• 1≤N≤2×10^5
• 1≤A_i≤10^9
• 所有输入值都是整数。

输入

输入将从标准输入以下格式给出：

N
A_1 A_2 … A_N

输出

打印他从N个怪物中获得的最大总经验点数，以整数形式输出。

样本输入1

5
1 5 3 2 7

样本输出1

28

如果高桥击败了第1、2、3和第5个怪物，并且放走了第4个怪物，他将获得以下经验点数：

• 击败了强度为A_1=1的怪物。他获得了1经验点。
• 击败了强度为A_2=5的怪物。他获得了5经验点。由于这是第2个被击败的怪物，他额外获得了5点。
• 击败了强度为A_3=3的怪物。他获得了3经验点。
• 放走了第4个怪物。高桥没有获得经验点。
• 击败了强度为A_5=7的怪物。他获得了7经验点。由于这是第4个被击败的怪物，他额外获得了7点。

因此，在这种情况下，他获得了1+(5+5)+3+0+(7+7)=28经验点。
注意，即使他遇到了一个怪物，如果他放它走，这不算是被击败。

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

样本输入2

2
1000000000 1000000000

样本输出2

3000000000

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