题目描述

有一个无限大的池塘，我们将其视为数轴。在这个池塘中，有 $N$ 朵睡莲漂浮在坐标 $0$，$1$，$2$，...，$N-2$ 和 $N-1$ 处。在坐标 $i$ 处的睡莲上写着一个整数 $s_i$。

你站在坐标 $0$ 处的睡莲上，你将进行以下游戏：

• $1$、选择正整数 $A$ 和 $B$。你的初始得分为 $0$。
• $2$、设 $x$ 是你当前的坐标，$y = x+A$。坐标 $x$ 处的睡莲消失，你移动到坐标 $y$ 处。
  • 如果 $y = N-1$，游戏结束。
  • 如果 $y \neq N-1$ 并且坐标 $y$ 处有一朵睡莲漂浮，你的得分增加 $s_y$。
  • 如果 $y \neq N-1$ 并且坐标 $y$ 处没有睡莲漂浮，你淹死。你的得分减少 $10^{100}$ 分，并且游戏结束。
• $3$、设 $x$ 是你当前的坐标，$y = x-B$。坐标 $x$ 处的睡莲消失，你移动到坐标 $y$ 处。
  • 如果 $y = N-1$，游戏结束。
  • 如果 $y \neq N-1$ 并且坐标 $y$ 处有一朵睡莲漂浮，你的得分增加 $s_y$。
  • 如果 $y \neq N-1$ 并且坐标 $y$ 处没有睡莲漂浮，你淹死。你的得分减少 $10^{100}$ 分，并且游戏结束。
• $4$、回到步骤 $2$。

你希望以尽可能高的分数结束游戏。选择 $A$ 和 $B$ 的最佳方法可以获得多少分？

约束条件

• $3 \leq N \leq 10^5$
• $-10^9 \leq s_i \leq 10^9$
• $s_0=s_{N-1}=0$
• 输入中的所有值都是整数。

输入

输入数据从标准输入读取，输入格式如下：

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

输出

打印选择 $A$ 和 $B$ 的最佳方法获得的分数。

示例输入1

5
0 2 5 1 0

示例输出1

3

如果选择 $A = 3$ 和 $B = 2$，游戏的进行如下：

• 移动到坐标 $0 + 3 = 3$。你的得分增加 $s_3 = 1$。
• 移动到坐标 $3 - 2 = 1$。你的得分增加 $s_1 = 2$。
• 移动到坐标 $1 + 3 = 4$。游戏以得分 $3$ 结束。

没有办法以得分 $4$ 或更高的分数结束游戏，因此答案是 $3$。注意，你不能降落在坐标 $2$ 处的睡莲上，否则后面会被淹死。

示例输入2

6
0 10 -7 -4 -13 0

示例输出2

0

这里的最佳策略是通过选择 $A = 5$（$B$ 的值无关紧要）立即降落在最后一朵睡莲上。

示例输入3

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

示例输出3

59