D - Bonus EXP Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

高橋君は N 匹のモンスターに順に出会います。i 匹目 (1\leq i\leq N) のモンスターの強さは A_i です。

高橋君はそれぞれのモンスターについて逃がすか倒すか選ぶことができます。
高橋君はそれぞれの行動によって次のように経験値を得ます。

  • モンスターを逃がした場合、得られる経験値は 0 である。
  • 強さが X のモンスターを倒したとき、経験値を X 得る。
    ただし、モンスターを倒すのが偶数回目（2, 4, \ldots 回目）であるとき、さらに追加で経験値を 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 匹目のモンスターを倒して、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

答えが 32bit 整数型に収まらない可能性があることに注意してください。

Score : 400 points

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.