P2314 [HNOI2005] 木梳
题目描述
$%$
$%$
艾艺从小酷爱艺术，他梦想成为一名伟大的艺术家。最近他获得了一块材质不错的木板，其下侧为直线段，长为 $L$，平均分为 $L$ 段，从左到右编号为 $1$、$2$、……、$L$。木板的上侧为锯齿形，高度为整数，第 $i$ 段的高度为 $A_i$，$A_i \ge 2$（如下图所示）。
```plain
*
* * *
* * * * * *
* * * * * * * *
* * * * * * * * *
* * * * * * * * *
4 4 6 5 4 2 3 3 5
```
这么好的一段材料浪费了怪可惜的，艾艺决定好好加工一番做成一件艺术品。但他不是纯艺术家，他觉得每件艺术品都应有实用价值（否则只是华而不实），具有实用性的艺术品是他设计的理念。
根据这块木板的锯齿状，艾艺想到了每天起床后都要用到的一件日用品，“对，就把它做成梳子！”他的设想是：用刻刀将某些上端的格子挖掉（如果把某个格子挖掉，那么这个格子上方的格子也必须被挖掉，但不能把一列中的格子全都挖掉）。使得剩下的木板构成“规则锯齿形”（这样才好梳头）。
例如，对上图，挖掉第 $3$、$7$、$8$ 列最上面的 $1$ 个格子和第 $5$ 列最上面的 $2$ 个格子后，剩下的区域就构成“规则锯齿形”（如下图所示）。
```plain
.
+---------+ +--->
| * * | | *
------------+ | |
* * * * | . | *
| |
* * * * | . . . | *
+-------------------------+
* * * * * * * * *
* * * * * * * * *
4 4 5 5 2 2 2 2 5
```
一个锯齿形称为“规则锯齿形”当且仅当它的边界（右图中红色曲线所示）的拐点序列不包含 `010` 或者 `101`。右图中曲线的拐点序列为 `011001`，其中 `0` 代表左拐，`1` 代表右拐，沿着曲线的最左端往右走，先左拐，再右拐，接着右拐，然后左拐，继续左拐，最后右拐。
为了最大限度地减少浪费，艾艺希望做出来的梳子面积最大。
输入格式
第一行一个整数 $L$，表示木板下侧直线段的长。
第二行为 $L$ 个正整数 $A_1 \sim A_L$，表示每段的高度。
输出格式
一个整数，表示为使梳子面积最大，需要从木板上挖掉的格子数。
说明/提示
对于 $50\%$ 的数据，$L \le 10^4$。
对于 $100\%$ 的数据，$4 \le L \le 10^5$，$2 \le A_i \le 10^8$。