### 问题描述

在执梗所生活的世界里，一周有 $N$ 天。他为每一天分配了"工作日"或"假日"的标签。这些分配在所有周中应该是相同的,并且至少有一天应该被分配为"假日"。

在这样的条件下，第 $i$ 天的工作效率定义如下：对于长度为 $N$ 的序列 $A$ ，如果第 $i$ 天是"假日"，其工作效率为 $0$ ；如果第 $i$ 天是"工作日"，其工作效率为 $A_{min(x,y)}$ ，其中上一个假日距离第 $i$ 天 $x$ 天，下一个假日距离第 $i$ 天 $y$ 天。

请注意，由于周期性的分配，上一个/下一个假日可能属于不同的周。

在选择最佳分配时，找出每周的最大工作效率。这里，每周的工作效率指的是每周第 $1$ 天、第 $2$ 天、...、第 $N$ 天的工作效率之和。

输入描述

第一行输入一个 $N$ ，表示一周的天数。

第二行输入 $N$ 个数字，第 $i$ 个数字表示 $A[i]$ 。

数据保证 $1 \leq N \leq 5000,1 \leq A[i] \leq 10^9$ 。

输出描述

输出一个数字表示最大效率。

样例输入

7
5 5 1 1 5 1 5

样例输出

25

说明

有一种方案是 $A[1]$ 和 $A[6]$ 休息，其余的五天工作，这样做效率为 $25$ 。可以证明没有效率更大的方案。