该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

怪物猎人

题目描述

高桥君要依次遇到 $N$ 只怪物。第 $i$ 只怪物的强度为 $A_i$。

对于每只怪物，高桥君可以选择以下两种行动之一：

1. 放走怪物：获得 $0$ 点经验值
2. 击败怪物：

• 击败强度为 $X$ 的怪物可获得 $X$ 点经验值
• 如果这是第偶数次击败怪物（第2次、第4次等），将额外获得 $X$ 点经验值

请计算高桥君可能获得的最大总经验值。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$。

输出格式

输出一个整数，表示可能获得的最大总经验值。

样例

5
1 5 3 2 7

28

2
1000000000 1000000000

3000000000

提示

样例1解释

以下是获得最大经验值的一种方案：

1. 击败第1只怪物（强度1）：获得1点经验值
2. 击败第2只怪物（强度5）：获得5+5=10点经验值（额外获得一次）
3. 击败第3只怪物（强度3）：获得3点经验值
4. 放走第4只怪物（强度2）：获得0点经验值
5. 击败第5只怪物（强度7）：获得7+7=14点经验值（额外获得一次）

总经验值为：$1+(5+5)+3+0+(7+7)=28$

注意：

• 如果击败所有怪物，总经验值为：$1+(5+5)+3+(2+2)+7=25$，这不是最优解
• 放走的怪物不计入击败次数

样例2解释

答案可能会超出32位整数范围。

数据范围与约定

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