硫酸钡之梦
题号：NC270861
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

硫酸钡做了一个梦，梦里他见到了神仙沙。
沙有很多魔法糖果，在硫酸钡的苦苦哀求以及再三保证以后会好好练习魔法后，沙终于松口同意硫酸钡带走一半的魔法糖果。
魔法糖果很珍贵，所以沙把每颗糖果都单独放在了一个展柜 a 中，展柜有 n 个线性排列的隔间编号 1 到 n，第 i 个隔间中魔法糖果的魔法值为 a_{i}。
沙要求硫酸钡从隔间中 a 中任意 [1,i] 的前缀中拿走和没拿走的糖果数相差值不大于 1，魔法糖果具有不同的魔法值，硫酸钡希望可以从糖果中获得尽可能多的魔法值，请问硫酸钡能获得的糖果魔法值之和的最大值。

输入描述:

第一行输入一个整数 n，代表糖果数目。

第二行输入 n 个数字 a_i，代表第 i 个展柜糖果的魔法值。

数据保证 1 \leq n \leq 10^5，1 \leq a_i \leq 10^9。

输出描述:

输出一个正整数，代表答案。
示例1

输入

复制 
4
1 5 4 3

输出

复制 
9

说明

选择第 2 个糖果和第 3 个糖果，糖果魔法值之和为 9。

其中前缀 [1,1] 中没拿走的糖果数目为 1，拿走的糖果数目为 0，相差值不大于于 1。

其中前缀 [1,2] 中没拿走的糖果数目为 1，拿走的糖果数目为 1，相差值不大于于 1。

其中前缀 [1,3] 中没拿走的糖果数目为 1，拿走的糖果数目为 2，相差值不大于于 1。

其中前缀 [1,4] 中没拿走的糖果数目为 2，拿走的糖果数目为 2，相差值不大于于 1。

可以证明该方案是最优方案。