AT_abc285_e [ABC285E] Work or Rest

高桥君所居住的世界中，一周有 $N$ 天。 一周的天数依次为星期 $1,2,\dots,N$，星期 $N$ 结束后，下一周从星期 $1$ 开始。 作为 ABC 国的国王，高桥君需要为每一天分配“工作日”或“休息日”。这种分配每周都必须相同。此外，必须至少有一天被分配为“休息日”。 在上述条件下，星期 $i$ 的产量通过长度为 $N$ 的数列 $A$ 定义如下： - 如果星期 $i$ 是“休息日”，则产量为 $0$。 - 如果星期 $i$ 是“工作日”，假设距离它最近的前一个休息日为 $x$ 天前，最近的后一个休息日为 $y$ 天后，则该天的产量为 $A_{\min(x,y)}$。 - 由于分配每周循环一次，最近的前/后休息日可能属于不同的周。具体请参见样例说明。 请你求出在合理分配的情况下，一周总产量的最大值。 这里一周总产量指的是星期 $1,2,\dots,N$ 的产量之和。

输入以如下格式从标准输入读入： > $N$ $A_1$ $A_2$ $\dots$ $A_N$

请输出最大的一周总产量，结果为整数。

## 限制条件 - 输入均为整数。 - $1\leq N\leq 5000$ - $1\leq A_i\leq 10^9$ ## 样例说明 1 例如，将星期 $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$ 或更高。 由 ChatGPT 4.1 翻译