配点 : $600$ 点

問題文

無限に広がる池があり、数直線とみなせます。この池には $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$ の値を決めたときの最終得点はいくらになるでしょうか。

制約

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

入力

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

$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