[ABC128F] Frog Jump

有 $n$ 朵荷花排成一排浮在水中，坐标为 $0$ 至 $n-1$。每朵荷花有一个属性值 $s_i$。 初始时，你的分数为 $0$，位于坐标 $0$ 处。你将进行如下操作（假设你现在位于坐标 $x$）： 1. 选择两个 **正整数** $A,B$。 2. 设 $y = x + A$。坐标 $x$ 处的莲花 **消失**，并分为如下三种情况： - $y=n-1$，操作结束。 - $y\ne n-1$，且此处有荷花，则你到达 $y$ 并获得 $s_y$ 的分数。 - $y\ne n-1$，但此处无荷花，则你淹死，得分减少 $10^{100}$，操作结束。 3. 设 $y=x-B$。坐标 $x$ 处荷花消失，同上。 你将重复执行 $2$ 操作以及 $3$ 操作，直至你淹死或者到了 $n-1$ 的位置。 你想知道能够获得的最大分数。 $3\le n\le 10^5$，$-10^9\le s_i\le 10^9$，$s_0=s_{n-1}=0$。

[problemUrl]: https://atcoder.jp/contests/abc128/tasks/abc128_f 無限に広がる池があり、数直線とみなせます。この池には $ 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 $ の値を決めたときの最終得点を出力してください。

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 $ の値は不問) ただちに最後の蓮に乗ることです。