题目描述

無限に広がる池があり、数直線とみなせます。この池には $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$ 増加する。
  • そこに蓮がないならば、あなたは溺れる。得点が $10^{100}$ 減少して、ゲームが終了する。

• 3.現在の位置を $x$ として、$y=x-B$とする。$x$ にある蓮を消して、$y$ に移動する。

  • $y=N-1$ ならば、ゲームが終了する。
  • そうでなくて、$y$ に蓮があるならば、得点が $s_y$ 増加する。
  • そこに蓮がないならば、あなたは溺れる。得点が $10^{100}$ 減少して、ゲームが終了する。

• 4.手順2に戻る。

あなたは、最終得点をできるだけ大きくしたいです。 最適に $A,B$ の値を決めたときの最終得点はいくらになるでしょうか。

输入格式

入力は以下の形式で標準入力から与えられます。

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

输出格式

最適に $A,B$ の値を決めたときの最終得点を出力してください。

题目大意

有一排荷花漂浮于水中，用它们表示一个数列 $s$，坐标 $0$ 到 $n-1$。你现在的分数为 $0$，当前为于坐标 $0$。

进行下列操作：

1.选择两个数 $A$ 和 $B$。

2.设 $y=x+A$，分三种情况：

• 若 $y = n-1$ 游戏结束。
• 若 $y \not= n-1$ 且 $y$ 点有荷花，你的分数加上 $s_{i}$。
• 若 $y \not= n-1$ 但否则你淹死，游戏结束

3.设 $y=x-B$，同上

请输出所能达到的最大分数。

5
0 2 5 1 0

3

6
0 10 -7 -4 -13 0

0

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

59

提示

制約

• $3\ \leqq\ N\ \leqq\ 10^5$
• $-10^9\ \leqq\ s_i\ \leqq\ 10^9$
• $s_0=s_{N-1}=0$
• 入力はすべて整数である。

Sample Explanation 1

$A\ =\ 3,\ B\ =\ 2$ としたとき、ゲームは次のように進行します。 - 座標 $0\ +\ 3\ =\ 3$ に移動し、得点が $s_3\ =\ 1$ 増加する。 - 座標 $3\ -\ 2\ =\ 1$ に移動し、得点が $s_1\ =\ 2$ 増加する。 - 座標 $1\ +\ 3\ =\ 4$ に移動し、得点 $3$ でゲームが終了する。 得点 $4$ 以上でゲームを終了することはできないため、答えは $3$ です。座標 $2$ にある蓮に乗ってその後溺れずに済ますことはできないことに注意してください。

Sample Explanation 2

ここでの最適な戦略は、$A\ =\ 5$ を選んで ($B$ の値は不問) ただちに最後の蓮に乗ることです。