题目描述

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

进行下列操作：

• 选择两个数 $A$ 和 $B$。

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

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

设 $y=x-B$，同上。

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

输入格式

第一行一个整数 $n$。

接下来 $n$ 个整数 $s_0, s_1, ... s_{n - 1}$。

输出格式

所能达到的最大分数。

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 \le n \le 10^5$，$-10^9 \le s_i \le 10^9$，$s_0 = s_{n - 1} = 0$。