City Planning

The city where Hyunwook lives has $N$ buildings. All the buildings stand in a single row, numbered $1$ through $N$ from the first building onward. The gap between adjacent buildings is $1$ everywhere. If the height of the $i$-th building is $H_i$, then when the row of buildings is viewed head-on, the $i$-th building can be represented as a line segment of zero thickness joining $(i, 0)$ and $(i, H_i)$.

For any $i$-th and $j$-th building, the two buildings can see each other's rooftops if the line segment joining the point $(i, H_i)$ representing the rooftop of the $i$-th building and the point $(j, H_j)$ representing the rooftop of the $j$-th building either does not meet any other building, or meets buildings only at their endpoints.

For example, suppose the city has 6 buildings with heights 2, 3, 7, 6, 1, 4 in order from the first building. Then, drawing each building as a line segment, the picture above can be drawn.

In the example, if we try to see the rooftop of the fourth building from the rooftop of the first building, the third building blocks the view as in the left side of the picture above, so the two rooftops cannot see each other. On the other hand, if we try to see the rooftop of the sixth building from the rooftop of the third building, the line joining the two rooftops meets the rooftop of the fourth building but only at an endpoint, so the two rooftops can see each other.

The mayor of the city where Hyunwook lives announced a new city plan one day. According to this plan, every building in the city must be able to see the rooftops of all other buildings from its rooftop.

Unfortunately, some buildings may have to be destroyed to satisfy this city plan. The mayor wants to minimize the number of destroyed buildings. Let us compute the minimum number of buildings that must be destroyed for the new city plan.

The first line gives the number of buildings in the city, $N$ ($1 \le N \le 2000$).

The second line gives the heights $H_i$ of the $N$ buildings in the city, from the leftmost building onward, separated by spaces ($1 \le H_i \le 10^9$).

On the first line, print the minimum number of buildings that must be destroyed to satisfy the condition.