在拜托克外星生物学研究所，刚刚成立了太空危险预警部门。受雇于该部门的科学家们的任务是竭尽全力保护拜托克公民免受即将到来的外星人入侵的影响。

拜托克有 $n$ 个城市，这些城市沿着拜托路依次排列。我们将城市依次编号为 $1$ 到 $n$。编号为 $i$ 的城市居住着 $a_{i}$ 名公民。

众所周知，外星人总是在夜间发动袭击，且每次至多袭击一个城市。不幸的是，他们的攻击是瞬间完成的——被袭击城市的所有居民会被迅速绑架并运送到外星人的星系。

研究所的科学家们正在研究如何保护居民。由于外星人对拜托克的啮齿动物毫无兴趣，科学家们决定利用经过训练的老鼠来警告拜托克其他城市。一旦某个城市被外星人袭击，两只老鼠会从该城市出发，沿拜托路向相反方向奔跑，传递袭击的信息。老鼠穿越拜托路的一段路程几乎需要一天，因此，从城市 $j$ 发送的消息会在袭击发生后第 $|k-j|$ 天傍晚之前，恰好传到城市 $k$。收到警报的居民会躲进避难所，外星人的触手将无法抓住他们。由于拜托克的避难所储备充足，被警告的居民会一直呆在里面，直到外星人停止袭击并返回自己的星系。

可以看出，这种系统并不一定能救下所有拜托克的公民。科学家们在思考，最坏情况下会有多少居民被绑架。

输入格式

输入的第一行包含一个整数 $n$（$1 \le n \le 1\,000\,000$），表示拜托克城市的数量。第二行包含 $a_{1}, \ldots, a_{n}$（$0 \le a_{i} \le 10^{9}$）这 $n$ 个整数，表示沿拜托路依次排列的各城市居民数。

输出格式

输出仅一行，包含一个整数，表示最多可能被绑架的居民数量。

样例

输入

6
5 9 1 3 7 2

输出

16