AT_abc369_d [ABC369D] Bonus EXP

[problemUrl]: https://atcoder.jp/contests/abc369/tasks/abc369_d 高橋君は $ N $ 匹のモンスターに順に出会います。$ i $ 匹目 $ (1\leq\ i\leq\ N) $ のモンスターの強さは $ A_i $ です。 高橋君はそれぞれのモンスターについて逃がすか倒すか選ぶことができます。 高橋君はそれぞれの行動によって次のように経験値を得ます。 - モンスターを逃がした場合、得られる経験値は $ 0 $ である。 - 強さが $ X $ のモンスターを倒したとき、経験値を $ X $ 得る。 ただし、モンスターを倒すのが偶数回目（$ 2 $, $ 4 $, $ \ldots $ 回目）であるとき、さらに追加で経験値を $ X $ 得る。 $ N $ 匹から高橋君が得た経験値の合計としてあり得る最大の値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

$ N $ 匹から高橋君が得た経験値の合計としてあり得る最大の値を整数で出力せよ。

### 制約 - $ 1\leq\ N\leq\ 2\times\ 10^5 $ - $ 1\leq\ A_i\leq\ 10^9 $ - 入力はすべて整数 ### Sample Explanation 1 $ 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 $ となります。 ### Sample Explanation 2 答えが $ 32 $bit 整数型に収まらない可能性があることに注意してください。