Tipover Transform

Tipover is a puzzle where blocks of different heights are placed on a $6 \times 6$ board and then knocked over so the hero can walk from the start to the goal. One day Sihun got bored while solving this puzzle and came up with the following $1$D Tipover game.

• The board is a row of $(N + 1)$ cells. Each cell is a $1\text{ cm}$ by $1\text{ cm}$ square, numbered from $0$ to $N$ from left to right.
• Each cell can hold at most one block. All blocks start standing upright. A standing block is a cuboid with a $1\text{ cm}$ width and depth and a height of at least $2\text{ cm}$. Each block height is an integer multiple of $1\text{ cm}$.
• A standing block can be knocked over to the left or to the right. If a block of height $k\text{ cm}$ is in cell $i$, knocking it to the left covers cells $(i-k)$ through $(i-1)$, and knocking it to the right covers cells $(i+1)$ through $(i+k)$. A block can be knocked over only if none of the cells it covers contain another block and all of the cells it covers are on the board. A knocked-over block cannot move again.
• Cell $0$ holds a block of height $1\text{ cm}$. The hero starts on cell $0$ and clears the game when reaching cell $N$. The hero can move only to adjacent cells, and only to cells that hold a block, regardless of the block height.

However, Sihun realized that some layouts cannot be cleared. So he added the following rules.

• Before the game starts, the hero can knock over some blocks in advance. There is no constraint on the order in which the blocks are knocked over.
• If no block is in a cell adjacent to the hero's cell, the hero can add a cube block of height $1\text{ cm}$ to that adjacent cell. A cube block cannot be knocked over.

Sihun wondered how few cube blocks are needed for the game on his board to be cleared. Solve this problem.

The first line contains $N$. ($3 \le N \le 300\,000$) The second line contains $N$ integers $A_1, A_2, \ldots, A_N$, separated by spaces. Each $A_i$ is either $0$ or an integer from $2$ to $N$. If $A_i = 0$, cell $i$ has no block at the start. If $A_i > 0$, cell $i$ has a block of height $A_i$ at the start.

Print the minimum number of cube blocks the hero must add to clear the game, when some blocks have been knocked over in advance.