题目描述

$$

$$

艾艺从小酷爱艺术，他梦想成为一名伟大的艺术家。最近他获得了一块材质不错的木板，其下侧为直线段，长为 $L$，平均分为 $L$ 段，从左到右编号为 $1$、$2$、……、$L$。木板的上侧为锯齿形，高度为整数，第 $i$ 段的高度为 $A_i$，$A_i \ge 2$（如下图所示）。

              *                                    
                                                   
              *     *                             *
                                                   
  *     *     *     *     *                       *
                                                   
  *     *     *     *     *           *     *     *
                                                   
  *     *     *     *     *     *     *     *     *
                                                   
  *     *     *     *     *     *     *     *     *
                                                   
  4     4     6     5     4     2     3     3     5

这么好的一段材料浪费了怪可惜的，艾艺决定好好加工一番做成一件艺术品。但他不是纯艺术家，他觉得每件艺术品都应有实用价值（否则只是华而不实），具有实用性的艺术品是他设计的理念。

根据这块木板的锯齿状，艾艺想到了每天起床后都要用到的一件日用品，“对，就把它做成梳子！”他的设想是：用刻刀将某些上端的格子挖掉（如果把某个格子挖掉，那么这个格子上方的格子也必须被挖掉，但不能把一列中的格子全都挖掉）。使得剩下的木板构成“规则锯齿形”（这样才好梳头）。

例如，对上图，挖掉第 $3$、$7$、$8$ 列最上面的 $1$ 个格子和第 $5$ 列最上面的 $2$ 个格子后，剩下的区域就构成“规则锯齿形”（如下图所示）。

              .                                      
            +---------+                         +--->
            | *     * |                         | *  
------------+         |                         |    
  *     *     *     * |   .                     | *  
                      |                         |    
  *     *     *     * |   .           .     .   | *  
                      +-------------------------+    
  *     *     *     *     *     *     *     *     *  
                                                     
  *     *     *     *     *     *     *     *     *  
                                                     
  4     4     5     5     2     2     2     2     5  

一个锯齿形称为“规则锯齿形”当且仅当它的边界（右图中红色曲线所示）的拐点序列不包含 010 或者 101。右图中曲线的拐点序列为 011001，其中 0 代表左拐，1 代表右拐，沿着曲线的最左端往右走，先左拐，再右拐，接着右拐，然后左拐，继续左拐，最后右拐。

为了最大限度地减少浪费，艾艺希望做出来的梳子面积最大。

输入格式

第一行一个整数 $L$，表示木板下侧直线段的长。

第二行为 $L$ 个正整数 $A_1 \sim A_L$，表示每段的高度。

输出格式

一个整数，表示为使梳子面积最大，需要从木板上挖掉的格子数。

9 
4 4 6 5 4 2 3 3 5

3

提示

对于 $50\%$ 的数据，$L \le 10^4$。

对于 $100\%$ 的数据，$4 \le L \le 10^5$，$2 \le A_i \le 10^8$。