Problem A
Bricklayer
Languages
en
pt
Rubens is a young bricklayer, he has learned many new techniques with his father, who is also his boss. They own a small construction and renovation company together. Since his father is getting old and the job requires a lot of physical effort, he wants to learn all the techniques his father knows so that he can only command the works himself.
Rubens’s father is a very experienced bricklayer, and thus has a very extensive knowledge in the subject, which results in the success of the company because customers are always satisfied with the service. This puts tremendous pressure on Rubens because he must always keep up with his father’s standards.
Rubens is on the current job without his father, to prove he is already capable handling the work by himself. But an unexpected event happened: it rained on the construction site. His father taught him that water puddles should never be left on the construction blocks, even if it is necessary to break some of them so the water can flow out.
As Rubens will have to rebuild the destroyed blocks, he wants to break as few blocks as possible. Also, if two blocks are in the same column, Rubens will only be able to destroy the bottom one after breaking the top one.
The current state of the construction can be modeled as $N$ columns of blocks, each with height $h_ i$. Given the current state of the job, help Rubens to calculate the least amount of blocks that must be destroyed for all the water to flow out.
The water flows whenever there are no obstacles (blocks above water level) on the right or left, and it accumulates when there are obstacles on both sides. It should be considered that the rain was uniform in all columns of blocks, and that it rained until the state of the puddles did not change anymore. For instance, consider the first example. There are five columns of blocks with the following heights: $5$, $2$, $3$, $4$, $5$. After raining the height of water puddles over the blocks will be: $0$, $3$, $2$, $1$, $0$, and for all water to flow, just break the top three blocks of the first column.
Input
The first line of the input contains an integer $N$ ($1 \leq N \leq 10^6$), which indicates the number of columns of blocks in the current state of the construction. The second line of the input contains $N$ integers $h_ i$ ($1 \leq h_ i \leq 10^ q$) representing the height of each column of blocks.
Output
Print a line containing only an integer, representing the minimum number of blocks that must be broken for all the water to flow out from the construction.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 5 2 3 4 5 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 2 5 10 9 8 7 |
0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 4 6 1 7 4 1 10 9 4 7 |
20 |
