Destruction of buildings#9029
There are buildings in Baku that have failed. On their place the new buildings should be built. For this you need to destroy the old buildings.
Barish is a specialist in the destruction of buildings. He has a super-robot that destroys buildings.
There are located next to each other buildings in the city . To destroy them, Barish took advantage of his robot.
Each of the buildings consists of blocks arranged one above the other. The robot must destroy all these blocks. In one move, the robot can destroy all external blocks. From these data, find the number of robot moves to destroy all buildings.
Block is called external, if at least in one of its directions (left, right, down, up) there is an empty space (for clarity, look at the picture)
First line contains the number of buildings (1 \leq n \leq 10^5). Next line contains the heights of buildings h_1, h_2, ... , h_n (1 \leq h_i \leq 10^9).
Print one integer - the number of moves required to destroy all buildings.
Example 1
Example 2
Illustration for the first example:
