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

题目描述

小S遇到了 $n$ 只怪物，依次遇到的第 $i$ 只怪物的经验值为 $a_i$ ，当小S击败这只怪物就会获得 $a_i$ 的经验值。

因为某种特殊的经验奖励，若一只怪物是第$k$个被击败的怪物，当$k$是偶数则会将该怪物的经验值翻倍。 为了得到最大的经验值，小S会按照顺序依次考虑每一只怪物，但是可以选择击败当前怪物，或者放走当前怪物，请你帮助他规划一个最好的选择使得得到的经验值尽可能大。

输入描述

输入只包含两行。
第一行为一个正整数$n$ , 表示怪物的数量。
第二行为$n$个正整数，第$i$个表示$a_i$。

输出描述

输出一个正整数，表示能得到的最大经验值。

输入输出样例

5
1 5 3 2 7

28

在击败第 1、2、3、5 只怪物并放走第 4 只怪物时，小S可以按如下方式获得经验值：

• 击败强度为 $A_1=1$ 的怪物，获得 $1$ 的经验值。
• 击败强度为 $A_2=5$ 的怪物，获得 $5$ 的经验值。这是小S 第 2 次击败怪物，因此额外获得 $5$ 的经验值。
• 击败强度为 $A_3=3$ 的怪物，获得 $3$ 的经验值。
• 放走第 4 只怪物，小S 不获得经验值。
• 击败强度为 $A_5=7$ 的怪物，获得 $7$ 的经验值。这是小S 第 4 次击败怪物，因此额外获得 $7$ 的经验值。

因此，总共获得的经验值为 $1+(5+5)+3+0+(7+7)=28$。
由于无论如何行动，总经验值都不会超过 $28$，所以输出 $28$。

请注意，如果击败所有怪物，获得的经验值为 $1+(5+5)+3+(2+2)+7=25$。

2
1000000000 1000000000

3000000000

数据范围描述

$1\leq\ n\leq\ 2\times\ 10^5$ $1\leq\ a_i\leq\ 10^9$