题目描述

有一个无限大的池塘，我们将其视为一条数轴。

在这个池塘上有$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$

接下来一共$N$个整数，分别表示睡莲上的$s_i$的值。

输出

输出$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

提示

$3 \leq N \leq 10^5$

$-10^9 \leq s_i \leq 10^9$

$s_0=s_{N-1}=0$