当前没有测试数据。

E - 工作还是休息

得分：500分

问题描述

Takahashi生活的世界中，一周有N天。

Takahashi是AtCoder王国的国王，他为每个工作日（weekday）或假期（holiday）指定了对应的日期。该指定应适用于所有的周，并且至少应有一天指定为假期。

在这样的情况下，第i天的生产力由长度为N的数组A来定义：

• 如果第i天是假期，则其生产力为0；
• 如果第i天是工作日，则其生产力是Amin(x, y)，其中x为上一个假期离第i天有x天，y为下一个假期离第i天有y天。

请找出在优选选择的情况下每周的最大生产力。这里，每周的生产力是指每周第1天，第2天，...，第N天的生产力之和。

约束条件

• 输入中的所有值都是整数。
• 1 ≤ N ≤ 5000
• 1 ≤ Ai ≤ 10^9

输入

输入以以下格式从标准输入给出：

N

A1 A2 ... AN

输出

将答案以整数形式输出。

示例

输入1

7
10 10 1 1 1 1 1

输出1

50

例如，我们可以选择将第2天和第4天指定为假期，其余的则指定为工作日，以使每周的生产力为50：

• 第1天：x=4，y=1，因此生产力为A1 = 10；
• 第2天：假期，生产力为0；
• 第3天：x=1，y=1，生产力为A1 = 10；
• 第4天：假期，生产力为0；
• 第5天：x=1，y=4，生产力为A1 = 10；
• 第6天：x=2，y=3，生产力为A2 = 10；
• 第7天：x=3，y=2，生产力为A2 = 10。

无法使每周的生产力达到51或更高。

输入2

10
200000000 500000000 1000000000 800000000 100000000 80000000 600000 900000000 1 20

输出2

5100000000

输入3

20
38 7719 21238 2437 8855 11797 8365 32285 10450 30612 5853 28100 1142 281 20537 15921 8945 26285 2997 14680

输出3

236980