← 返回题目列表

AtCoder · abc369_d

G. 额外经验值

中文机器翻译题面 查看原题

分数: 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位整数。