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

题目背景

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

题目描述

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
-5 2

-3

• Kitten 可以选择在城市 1 声东击西，发动后 $1$ 分钟 33DAI 会到，此时 Kitten 可以前往城市 2，并停在城市 2。
• Kitten 可以选择在城市 2 声东击西，发动后 $2$ 分钟 33DAI 会到，此时 Kitten 可以前往城市 1，并停在城市 1。

显然得分一样。

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

14

可以从城市 8 声东击西，这样第 $8$ 分钟才会封锁城市 $8$。发动后可以按照 8->9->10->9->8->7->6->5->4 的路径走，路途中没有被封锁。

6
-1000 100 -1000 -10 90 -10

80

可以在城市 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 分）：没有特殊限制。