该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

敌志乱萃，不虞，坤下兑上之象，利其不自主而取之。

Description

33DAI 和 Kitten 正在玩一款游戏。游戏中有 $n$ 个城市($n\gt 1$)，从左到右编号从 $1\sim n$，编号为 $i$ 的城市有 $a_i$ 的资源。

Kitten 可以任选一个城市开始实行声东击西战略，假设她选择城市 $x$。那么 33DAI 就会警觉并前往城市 $x$。这需要花费 33DAI $x$ 分钟的时间。33DAI 到达后就会封锁城市 $x$ 使得不能从 $x-1$ 走到 $x$，也不能从 $x+1$ 走到 $x$。如果此时 Kitten 就在城市 $x$，那么 Kitten 就会直接输掉游戏。

Kitten 每分钟可以选择待在原地或者走到左边或者右边的城市（即从城市 $i$ 走到城市 $i+1$ 或 $i-1$）。

请你帮 Kitten 决定起始城市及每分钟的移动策略，来不输掉游戏，并最大化她到过的城市资源之和。

Format

Input

第一行为一个数 $n$。

第二行为 $n$ 个整数 $a_1\sim a_n$。

Output

一个整数，即她到过的城市资源之和的最大值。

Samples

2
-5 2

-3

10
2 2 -100 2 2 2 2 2 2 2

14

6
-1000 100 -1000 -10 90 -10

80

Limitation

对于 $100\%$ 的数据，$2 \le n \le 10^6$，$-10^9\le a_i\le 10^9$。