问题 P: 蛙跳

内存限制：128 MB 时间限制：1.000 S

评测方式：文本比较命题人：

提交：104 解决：36

小T在第七共和国的中心大楼发生了爆炸之后重生了，他发现他现在是一只青蛙，如果要重新变回人类，他需要解决这道问题

有无限广阔的池塘，可以看作是一条直线。

这个池塘里漂浮着n个莲花，它们的坐标为0,1,.....n-1.。你在最初坐标0的莲花上。

你将进行如下操作若干次：

选定任意的2个正整数A, ，初始分数为0。假设当前位置为x：
你的坐标移动到 x + A 这个位置上，并且y = x + A
- 如果y=N−1，游戏结束。
- 如果y≠N−1，但是y这个莲花存在，那么分数增加si，并且这片莲花消失。
- 如果y≠N−1，但是y这个莲花不存在，那么分数减去10的100次方，游戏结束。
你的坐标移动到 x - B 这个位置上，并且y = x - B

问你如何选择A,B 可以让最后的得分最大，输出该得分

n
$s_0$ $s_1$ .......$s_{n-1}$

1 <= n <= 1e5(100000)
-1e9 <= si <= 1e9 (1后面9个0）
$s_0$ = $s_{n-1}$ = 0

问选定最优的A、

B的情况下，得到的最高分数为多少？

5
0 2 5 1 0

如果选择A=3和B=2，

游戏按如下方式进行：

移动到坐标0 + 3 = 3。

你的分数增加s3 = 1分 .

移到坐标3−2=1.

你的分数增加s1 =2.

移动到坐标1+3=4。

4 = n - 1 所以

比赛以3分结束。

没有办法以4分或更高的分数结束比赛，所以答案是3分。

请注意，您不能在坐标2处降落莲花，否则稍后会溺水。