题目描述

高橋君が住む世界の一週間は $N$ 日からなります。
一週間は曜日 $1,2,\dots,N$ と進んでいき、曜日 $N$ が終わると次の週の曜日 $1$ が始まります。

ABC 国の国王である高橋君は、各曜日に「平日」「休日」のどちらかを割り当てます。この割り当ては毎週同じでなければなりません。また、少なくとも $1$ つの曜日を「休日」に割り当てなければなりません。

この条件の下で、曜日 $i$ の生産量は長さ $N$ の数列 $A$ を用いて以下のように定義されます。

• 曜日 $i$ が「休日」である場合は $0$
• 曜日 $i$ が「平日」のとき、直前の休日が $x$ 日前、直後の休日が $y$ 日後である場合は $A_{\min(x,y)}$
  • 割り当ては毎週繰り返されるため、 直前 / 直後 の「休日」が当日とは別の週に属する可能性があることに注意してください。詳しくはサンプルを参照してください。

上手く割り当てを決めたときの一週間当たりの生産量の最大値を答えてください。
但し、一週間当たりの生産量とは曜日 $1,2,\dots,N$ の生産量の総和を指します。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを整数として出力せよ。

题目大意

在一个王国中一周有 $n$ 天，有 $n$ 个数 $a_i$。每一天可以是工作日，也可以是休息日。对于每一个工作日可以产生 $a_{min(x,y)}$ 的工作量，其中 $x$ 是距离前一个休息日的天数，$y$ 是距离后一个休息日的天数。休息日没有任何工作量。每周至少有一天是休息日。求最大工作量。注：一天的前一个或后一个休息日可能在上一周或下一周。

7
10 10 1 1 1 1 1

50

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$

Sample Explanation 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$ 以上にすることはできません。