#}. 工作还是休息

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在高桥生活的世界里，一周有 $N$ 天。

高桥是一家公司的老板，他要决定每一周当中哪几天是工作日，哪几天是休息日。一周当中至少要有一天是休息日。

对于每个 $i$ （ $1\le i\le N$ ），每一周的第 $i$ 天人的工作效率由一个长为 $N$ 的整数序列 $A$ 决定，规则如下。若第 $i$ 天是休息日，工作效率是 $0$ ；

若第 $i$ 天是工作日，工作效率是 $A_{\min(x,y)}$ ，若上一个休息日是 $x$ 天之前，下一个休息日是 $y$ 天之后。求一周当中每一天的工作效率之和的可能达到的最大值。

$N$

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

输出答案。

7

10 10 1 1 1 1 1

样例一解释

让每周的第2天和第4天是休息日，其他天是工作日，可以达到一周的工作效率是50。

第1天：x = 4，y = 1， $A_{1} = 10$

第3天：x = 1，y = 1， $A_{1} = 10$

第5天：x = 1，y = 4， $A_{1} = 10$

第6天：x = 2，y = 3， $A_{2} = 10$

第7天：x = 3，y = 2， $A_{2} = 10$