资源和

题目描述

小珅和 Kitten 正在玩一款游戏。游戏中有 $n$个城市（$n>1$），从左到右编号从 $1 \sim n$，编号为 $i$的城市有 $a_i$的资源。Kitten 可以任选一个城市开始实行声东击西战略，假设她选择城市 $x$。那么小珅就会警觉并前往城市 $x$。这需要花费小珅 $x$分钟的时间。小珅到达后就会封锁城市 $x$，使得不能从 $x-1$走到 $x$，也不能从 $x+1$走到 $x$。如果此时 Kitten 就在城市 $x$，那么 Kitten 就会直接输掉游戏。

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

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

输入格式

第一行为一个数 $n$。

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

输出格式

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

输入输出样例

输入 #1

2 -5 2

输出 #1

-3

输入 #2

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

输出 #2

14

输入 #3

6 -1000 100 -1000 -10 90 -10

输出 #3

80

说明/提示

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

子任务 $1$（$10$分）：保证 $n = 2$。

子任务 $2$（$20$分）：保证 $a_i \ge 0$。

子任务 $3$（$30$分）：保证 $n = 100$。

子任务 $4$（$40$分）：没有特殊限制。