#A0638. 声东击西

声东击西

题目背景

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

题目描述

33DAI 和 Kitten 正在玩一款游戏。游戏中有 nn 个城市(n>1n\gt 1),从左到右编号从 1n1\sim n,编号为 ii 的城市有 aia_i 的资源。

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

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

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

输入格式

第一行为一个数 nn

第二行为 nn 个整数 a1ana_1\sim a_n

输出格式

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

2
-5 2
-3
  • Kitten 可以选择在城市 1 声东击西,发动后 11 分钟 33DAI 会到,此时 Kitten 可以前往城市 2,并停在城市 2。
  • Kitten 可以选择在城市 2 声东击西,发动后 22 分钟 33DAI 会到,此时 Kitten 可以前往城市 1,并停在城市 1。

显然得分一样。

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

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

6
-1000 100 -1000 -10 90 -10
80

可以在城市 6 发动声东击西,然后前往城市 5 待着不动。

数据规模与约定

对于 100%100\% 的数据,2n1062 \le n \le 10^6109ai109-10^9\le a_i\le 10^9

  • 子任务 1(10 分):保证 n=2n=2
  • 子任务 2(20 分):保证 ai>=0a_i>=0
  • 子任务 3(30 分):保证 n=100n=100
  • 子任务 4(40 分):没有特殊限制。