题目描述

There is an infinitely large pond, which we consider as a number line. In this pond, there are $N$ lotuses floating at coordinates $0$, $1$, $2$, ..., $N-2$ and $N-1$. On the lotus at coordinate $i$, an integer $s_i$ is written.

You are standing on the lotus at coordinate $0$. You will play a game that proceeds as follows:

• $1$. Choose positive integers $A$ and $B$. Your score is initially $0$.
• $2$. Let $x$ be your current coordinate, and $y = x+A$. The lotus at coordinate $x$ disappears, and you move to coordinate $y$.
  • If $y = N-1$, the game ends.
  • If $y \neq N-1$ and there is a lotus floating at coordinate $y$, your score increases by $s_y$.
  • If $y \neq N-1$ and there is no lotus floating at coordinate $y$, you drown. Your score decreases by $10^{100}$ points, and the game ends.
• $3$. Let $x$ be your current coordinate, and $y = x-B$. The lotus at coordinate $x$ disappears, and you move to coordinate $y$.
  • If $y = N-1$, the game ends.
  • If $y \neq N-1$ and there is a lotus floating at coordinate $y$, your score increases by $s_y$.
  • If $y \neq N-1$ and there is no lotus floating at coordinate $y$, you drown. Your score decreases by $10^{100}$ points, and the game ends.
• $4$. Go back to step $2$.

You want to end the game with as high a score as possible. What is the score obtained by the optimal choice of $A$ and $B$?

有一个无限大的池塘，我们把它看作一条数线。在这个池塘里，有 $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$ 中做出最优选择得到的分数是多少？

输入格式

输入内容按以下格式标准输入：

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

输出格式

打印 $A$ 和 $B$ 的最优选择所得到的分数。

样例 #1

样例输入 #1

5
0 2 5 1 0

样例输出 #1

3

样例 #2

样例输入 #2

6
0 10 -7 -4 -13 0

样例输出 #2

0

样例 #3

样例输入 #3

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

样例输出 #3

59

说明

数据规模与约定

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

样例 $1$ 解释

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

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

不可能以 $4$ 或更高的分数结束游戏，因此答案是 $3$ 。请注意，在坐标 $2$ 处着陆莲花是不会被淹死的。

样例 $2$ 解释

这里的最佳策略是选择 $A = 5$ 立即下出最后的莲子（ $B$ 的值并不重要）。