木梳
时限1s
问题描述：
King从小就酷爱艺术，他梦想成为一名伟大的艺术家。最近他得到了一块材质不错的木板，木板下侧为直线段，长为L，平均分为L段，从左到右编号为1，2，……，L。木板的上侧是锯齿形，高度为整数，第i段的高度为Ai，Ai>=2。（如右所示）
这么好的一段材料浪费了怪可惜的，King决定好好加工一番做成一件艺术品。但他不是纯艺术家，他觉得每一件作品都应该有实用价值（否则只是华而不实），具有实用性的艺术品是他设计的理念。
根据这块木板的锯齿状，King想到了每天起床后都要用到的一件日用品，“对，就把它做成梳子！”他的设想是：用刻刀将某些上端的格子挖掉（如果把某个格子挖掉，那么这个格子上方的格子也必须被挖掉，但不能把一列中的格子全都挖掉），使得剩下木板构成“规则锯齿形”（这样才好梳头）。
例如，对于上图，挖掉第3，7，8列最上面1个格子，第5列最上面2个格子后，剩下的区域就构成“规则锯齿形”（如右图）。一个锯齿形称为“规则锯齿形”当且仅当它的上边界（图中红色曲线所示）的拐弯序列不包含“010”或者“101”。图中红色曲线的拐弯序列为：“011001”，（其中0代表往左拐，1代表往右拐）沿着曲线的最左端往右走，先左拐，再右拐，接着右拐，然后左拐，继续左拐，最后右拐。
为了最大限度的减少浪费，King希望做出来的梳子面积最大。这样一来，设计梳子的任务就变得非常复杂了——不过这是对于艺术家来说，对于你来说，不就是小菜一碟吗？
输入数据：
第一行一个整数L；
第二行L个正整数A1,A2,…,AL。1<Ai<=108。
输出数据：
输出一个整数D，表示：为使梳子的面积最大，最少需要从木板上挖掉的格子数。
数据范围：4<=L<=100000。有50%的数据满足L<=104。
输入示例#1：
9
4 4 6 5 4 2 3 3 5（方案如右图）
输出示例#1：
3
输入示例#2：
4
2 100 10000 1000000
输出示例#2：
9901（方案为：挖掉第3列最上方的9901个格子）
