Destruction of buildings

Destruction of buildings

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 roads. He has a super-robot that destroys buildings.

There are n 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 4 directions (left, right, down, up) there is an empty space (for clarity, look at the picture)


First line contains the number of buildings n (1n105). Next line contains the heights of buildings h1, h2, ... , hn (1hi109).


Print one integer - the number of moves required to destroy all buildings.


The picture below explains the first test case


Time limit 1 second
Memory limit 128 MiB
Input example #1
2 1 4 6 2 2

Output example #1
Input example #2
3 3 3 1 3 3 3

Output example #2
Author Rashad Mammadov
Source 2019 İOİ Selection Round of Azerbaijan team