题目描述
【题目背景】
敌志乱萃，不虞，坤下兑上之象，利其不自主而取之。
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 决定起始城市及每分钟的移动策略，来不输掉游戏，并最大化她到过的城市资源之和。
输入
第一行为一个数 $n$。
第二行为 $n$ 个整数 $a_1\sim a_n$。
输出
一个整数，即她到过的城市资源之和的最大值。
样例输入输出
输入#2
复制
10
2 2 -100 2 2 2 2 2 2 2
输入#3
复制
6
-1000 100 -1000 -10 90 -10
提示
【样例1解释】
- Kitten 可以选择在城市 1 声东击西，发动后 $1$ 分钟 33DAI 会到，此时 Kitten 可以前往城市 2，并停在城市 2。
- Kitten 可以选择在城市 2 声东击西，发动后 $2$ 分钟 33DAI 会到，此时 Kitten 可以前往城市 1，并停在城市 1。
显然得分一样。
【样例2解释】
可以从城市 8 声东击西，这样第 $8$ 分钟才会封锁城市 $8$。发动后可以按照 `8->9->10->9->8->7->6->5->4` 的路径走，路途中没有被封锁。
【样例3解释】
可以在城市 6 发动声东击西，然后前往城市 5 待着不动。
【数据规模与约定】
对于 $100\%$ 的数据，$2 \le n \le 10^6$，$-10^9\le a_i\le 10^9$。
- 子任务 1（10 分）：保证 $n=2$。
- 子任务 2（20 分）：保证 $a_i>=0$。
- 子任务 3（30 分）：保证 $n=100$。
- 子任务 4（40 分）：没有特殊限制。