问题描述

在高桥所在的世界中，一周有 $N$ 天。

高桥是 AtCoder 王国的国王，在每天周期性的工作日与假日之间进行分配。这个分配对于所有的周期必须是相同的，并且至少有一天被指定为假日。

在这样的条件下，第 $i$ 天的产出率由长度为 $N$ 的序列 $A$ 定义如下：

• 如果第 $i$ 天是“假日”，那么它的产出率为 $0$；
• 如果第 $i$ 天是“工作日”，那么它的产出率为 $A_{\\min(x,y)}$，其中最后一个假日是 $x$ 天前，下一个假日是 $y$ 天后。
  • 注意，由于周期性的分配，最后一个/下一个假日可能属于不同的周期。详情请参见示例。

当选择最优的分配时，找到每周的最大产出率。
这里，每周的产出率指的是第 1 天、第 2 天、……、第 $N$ 天的产出率之和。

约束条件

• 输入中的所有值都是整数。
• $1 \\le N \\le 5000$
• $1 \\le A_i \\le 10^9$

输入

从标准输入读入数据，输入格式如下：

$N$ $A_1$ $A_2$ $\\dots$ $A_N$

输出

以整数形式打印答案。

示例输入1

7
10 10 1 1 1 1 1

示例输出1

50

例如，我们可以将第 2 天和第 4 天指定为假日，其余的天数指定为工作日，以达到每周产出率为 $50$：

• 第 1 天……$x=4$ 且 $y=1$，因此产出率为 $A_1 = 10$。
• 第 2 天……它是假日，所以产出率为 $0$。
• 第 3 天……$x=1$ 且 $y=1$，因此产出率为 $A_1 = 10$。
• 第 4 天……它是假日，所以产出率为 $0$。
• 第 5 天……$x=1$ 且 $y=4$，因此产出率为 $A_1 = 10$。
• 第 6 天……$x=2$ 且 $y=3$，因此产出率为 $A_2 = 10$。
• 第 7 天……$x=3$ 且 $y=2$，因此产出率为 $A_2 = 10$。

无法使每周产出率大于或等于 $51$。

示例输入2

10
200000000 500000000 1000000000 800000000 100000000 80000000 600000 900000000 1 20

示例输出2

5100000000

示例输入3

20
38 7719 21238 2437 8855 11797 8365 32285 10450 30612 5853 28100 1142 281 20537 15921 8945 26285 2997 14680

示例输出3

236980