莲花

题目描述

有一个无限延伸的池塘,可以看作一条数轴。池塘里浮着 $N$ 片莲花,它们位于坐标 $0,1,2,...,N-2,N-1$ 处。

你最初站在坐标 $0$ 的莲花上。你决定按照以下步骤进行游戏:

• 1. 确定正整数 $A,B$。得分一开始为 $0$。
• 2. 设当前位置为 $x$,令 $y=x+A$。消去位于 $x$ 的莲花,移动到 $y$。
  • 若 $y=N-1$,游戏结束。
  • 否则,若 $y$ 处有莲花,则得分增加 $s_y$。
  • 若 $y$ 处没有莲花,你会溺水。得分减少 $10^{100}$,游戏结束。
• 3. 设当前位置为 $x$,令 $y=x-B$。消去位于 $x$ 的莲花,移动到 $y$。
  • 若 $y=N-1$,游戏结束。
  • 否则,若 $y$ 处有莲花,则得分增加 $s_y$。
  • 若 $y$ 处没有莲花,你会溺水。得分减少 $10^{100}$,游戏结束。
• 4. 回到步骤 2。

你想让最终得分尽可能大。当最优地确定 $A,B$ 的值时,最终得分是多少?

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出当最优地确定 $A,B$ 的值时的最终得分。

样例

5
0 2 5 1 0

3

取 $A = 3, B = 2$ 时,游戏按如下方式进行:

• 移动到坐标 $0 + 3 = 3$,得分增加 $s_3 = 1$。

• 移动到坐标 $3 - 2 = 1$,得分增加 $s_1 = 2$。

• 移动到坐标 $1 + 3 = 4$,得分为 $3$,游戏结束。

无法以 $4$ 分或以上的得分结束游戏,因此答案是 $3$。注意:不能坐上坐标 $2$ 的莲花后不溺水地继续游戏。

6
0 10 -7 -4 -13 0

0

这里的最优策略是选择 $A = 5$($B$ 的值任意),立刻坐上最后一片莲花。

11
0 -4 0 -99 31 14 -15 -39 43 18 0

59

数据范围

• $3 \le N \le 10^5$
• $-10^9 \le s_i \le 10^9$
• $s_0 = s_{N-1} = 0$
• 输入均为整数。