题目描述

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

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

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

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

• 输入的值都是整数。
• $1 \le N \le 5000$
• $1 \le A_i \le 10^9$

输入格式

$N$

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

输出格式

输出答案。

7

10 10 1 1 1 1 1

50

样例一解释

让每周的第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$