分数: 400 点
问题陈述
高桥会遇到 N 怪物按顺序排列。的 i- 第一个怪物 (1\leq i\leq N) 的实力为 A_i.
对于每个怪物,他可以选择放走它或击败它。
每个动作都会奖励他经验值,如下:
- 如果他放走怪物,他会获得 0 经验值。
- 如果他以力量击败怪物 X,他获得 X 经验值。
如果是偶数个被击败的怪物(第2,第4,...),他额外获得一个 X 经验值。
找出他可以从 N 怪物。
约束
- 1\leq N\leq 2\times 10^5
- 1\leq A_i\leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N
输出
打印他可以从 N 怪物数量为整数。
示例输入 1
5 1 5 3 2 7
示例输出 1
28
如果高桥击败第1、2、3、5只怪物,并放走第四只怪物,他将获得如下经验值:
- 用力量打败怪物 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
2 1000000000 1000000000
示例输出 2
3000000000
请注意,答案可能不适合 32位整数。