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)

Input

First line contains the number of buildings n (1 ≤ n ≤ 105). Next line contains the heights of buildings h1, h2, ... , hn (1 ≤ hi ≤ 109).

Output

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

Explanation

The picture below explains the first test case