工作还是休息 - 代码源竞赛平台

题目描述

蜗蜗管理的王国里，一周有 $N$ 天，按第 $1$ 天到第 $N$ 天循环。他要把每个星期几固定安排为工作日或休息日，此安排每周相同，并且一周至少有一天休息。

休息日的产量为 $0$。对于工作日，若距离它最近的前一个休息日有 $x$ 天，距离它最近的后一个休息日有 $y$ 天，当天产量为 $A_{\min(x,y)}$。由于安排每周循环，前一个或后一个休息日可能在相邻的星期。

求一周内 $N$ 天的最大总产量。

输入格式

第一行包含一个整数 $N$，表示一周的天数。

第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$，表示对应距离的工作日产量。

输出格式

输出一行一个整数，表示一周的最大总产量。

样例

3
1 2 3

2

1
10

0

样例解释

样例 1 中，可安排第 $1$ 天休息，其余两天工作。两个工作日离最近休息日都是 $1$ 天，产量共为 $1+1=2$。

样例 2 中，一周只有一天，这一天必须休息，因此产量为 $0$。

数据范围

对于 100% 的数据，保证 $1\le N\le 5000$，$1\le A_i\le 10^9$。