You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Frog Jump

题目描述

有 $n$ 朵荷花排成一排浮在水中，坐标为 $0$ 至 $n-1$。每朵荷花有一个属性值 $s_i$。

初始时，你的分数为 $0$，位于坐标 $0$ 处。你将进行如下操作：

1. 选择两个 正整数 $A,B$。
2. 假设你现在位于坐标 $x$ ，设 $y = x + A$。你移动至坐标 $y$ ，坐标 $x$ 处的莲花 消失，并分为分如下三种情况：

• $y=n-1$，操作结束。
• $y\ne n-1$，且此处有荷花，则你获得 $s_i$ 的分数。
• $y\ne n-1$，但此处无荷花，则你淹死，操作结束。

3. 假设你现在位于坐标 $x$ ，设 $y=x-B$。你移动至坐标 $y$ ，坐标 $x$ 处荷花消失，分类讨论同上。

你将重复执行 $2$ 操作以及 $3$ 操作，直至你淹死或者到了 $n-1$ 的位置，且必须恰好到 $n-1$ 的位置。

你想知道在不能淹死的前提下，你能够获得的最大分数。

输入格式

输入格式如下，第一行一个整数 $N$ ，第二行 $N$ 个用空格分隔的整数 $s_i$ 。

$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\ \leqq\ N\ \leqq\ 10^5$
• $-10^9\ \leqq\ s_i\ \leqq\ 10^9$
• $s_0=s_{N-1}=0$
• 输入都是整数。

样例解释 1

取 $A=3,B=2$ 。则先往前 $3$ 步到 $4$ 号荷叶上得 $2$ 分，再后退 $2$ 步到 $2$ 号荷叶上得 $1$ 分，最后往前 $3$ 步到达 $5$ 号荷叶，总共得到 $3$ 分。