Description

$$

$$

Ai Yi has loved art since childhood and dreams of becoming a great artist. Recently, he got a nice wooden board whose bottom side is a straight segment of length $L$, evenly divided into $L$ segments, numbered $1, 2, \ldots, L$ from left to right. The top side is a sawtooth shape with integer heights: the height of the $i$-th segment is $A_i$, where $A_i \ge 2$ (see the figure below).

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

It would be a pity to waste such good material, so Ai Yi decides to craft it into a piece of art. But he is not a pure artist; he believes every artwork should be practical (otherwise it is merely flashy). Practicality is his design philosophy.

Inspired by the sawtooth shape of the board, Ai Yi thought of an everyday item used after getting up: “Yes, let’s make it into a comb!” His idea is to chisel away some cells at the top ends of columns (if a cell is removed, then all cells above it must also be removed, but you cannot remove all cells in any column), so that the remaining board forms a “regular sawtooth shape” (which is suitable for combing).

For example, for the figure above, if you remove the top $1$ cell from columns $3$, $7$, and $8$, and remove the top $2$ cells from column $5$, the remaining region forms a “regular sawtooth shape” (as shown below).

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

A sawtooth shape is called “regular” if and only if the turning sequence of its boundary (the red curve in the right figure) does not contain 010 or 101. In the right figure, the curve’s turning sequence is 011001, where 0 denotes a left turn and 1 denotes a right turn. Walking along the curve from the leftmost end to the right, you first turn left, then right, then right, then left, then left, and finally right.

To minimize waste, Ai Yi wants the comb’s area to be as large as possible.

Input Format

The first line contains an integer $L$, the length of the bottom straight segment of the board.

The second line contains $L$ positive integers $A_1 \sim A_L$, the heights of each segment.

Output Format

Output a single integer: the number of cells that must be removed from the board so that the comb’s area is maximized.

9 
4 4 6 5 4 2 3 3 5

3

Hint

For $50\%$ of the testdata, $L \le 10^4$.

For $100\%$ of the testdata, $4 \le L \le 10^5$, $2 \le A_i \le 10^8$.

Translated by ChatGPT 5