工作日与休息日

题目描述

在 Takahashi 生活的世界里,一周有 $N$ 天。

Takahashi 是 AtCoder 王国的国王,他给一周中的每一天指定「工作日」或「休息日」。每周的指定必须相同,且至少有一天被指定为「休息日」。

在这样的条件下,一周中第 $i$ 天的生产力由长度为 $N$ 的序列 $A$ 定义如下:

• 如果第 $i$ 天是「休息日」,生产力为 $0$;
• 如果第 $i$ 天是「工作日」,设最近的前一个休息日在 $x$ 天前、下一个休息日在 $y$ 天后,则生产力为 $A_{\min(x,y)}$。

注意,由于指定是周期性重复的,前一个/后一个休息日可能属于其他周。详见样例。

在最优指定下,求每周的最大生产力。

这里,每周的生产力指第 $1, 2, \dots, N$ 天的生产力之和。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出答案的整数。

样例

7
10 10 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$ 或更大。

10
200000000 500000000 1000000000 800000000 100000000 80000000 600000 900000000 1 20

5100000000

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

236980

数据范围

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