팁오버 변환

팁오버는 $6 \times 6$ 크기의 보드판에 높이가 다른 블록을 배치한 뒤 블록을 쓰러뜨려, 주인공이 출발지에서 목적지까지 이동할 수 있게 만드는 퍼즐 게임이다. 어느 날 이 퍼즐을 풀던 시헌이는 지루해져서 다음과 같은 $1$차원 팁오버 게임을 생각해냈다.

• 보드판은 $(N + 1)$개의 칸이 일렬로 늘어선 구조다. 각 칸은 가로와 세로가 $1\text{ cm}$인 정사각형이며, 왼쪽부터 차례로 $0$부터 $N$까지 번호가 붙는다.
• 각 칸에는 블록이 최대 한 개 놓일 수 있다. 모든 블록은 처음에 세워져 있다. 세워진 블록은 가로와 세로가 각각 $1\text{ cm}$이고 높이가 $2\text{ cm}$ 이상인 직육면체다. 각 블록의 높이는 $1\text{ cm}$의 정수 배다.
• 세워진 블록은 왼쪽이나 오른쪽으로 쓰러뜨릴 수 있다. $i$번 칸에 높이가 $k\text{ cm}$인 블록이 있을 때, 왼쪽으로 쓰러뜨리면 $(i-k)$번 칸부터 $(i-1)$번 칸까지를 덮고, 오른쪽으로 쓰러뜨리면 $(i+1)$번 칸부터 $(i+k)$번 칸까지를 덮는다. 블록이 덮는 칸에 다른 블록이 없고 덮는 칸이 모두 보드판 안에 있을 때에만 그 블록을 쓰러뜨릴 수 있다. 쓰러뜨린 블록은 더 이상 움직일 수 없다.
• $0$번 칸에는 높이가 $1\text{ cm}$인 블록이 있다. 주인공은 처음에 $0$번 칸 위에 있으며, $N$번 칸에 도착하면 게임을 클리어할 수 있다. 주인공은 인접한 칸으로만 이동할 수 있고, 블록 높이와 관계없이 블록이 놓인 칸으로만 이동할 수 있다.

하지만 시헌이는 게임을 클리어할 수 없는 배치가 있다는 것을 깨달았다. 그래서 다음 규칙을 추가했다.

• 주인공은 게임을 시작하기 전에 블록을 몇 개 미리 쓰러뜨릴 수 있다. 블록을 쓰러뜨리는 순서에는 제약이 없다.
• 주인공이 있는 칸과 인접한 칸에 블록이 없으면, 주인공은 그 인접한 칸에 높이가 $1\text{ cm}$인 큐브 블록을 추가할 수 있다. 큐브 블록은 쓰러뜨릴 수 없다.

시헌이는 자신이 만든 보드판에서 게임을 진행할 때 큐브 블록이 최소 몇 개 있어야 클리어할 수 있는지 궁금해졌다. 이 문제를 해결하라.

첫째 줄에 $N$이 주어진다. ($3 \le N \le 300\,000$) 둘째 줄에 $N$개의 정수 $A_1, A_2, \ldots, A_N$이 공백으로 구분되어 주어진다. $A_i$는 $2$ 이상 $N$ 이하의 정수이거나 $0$이다. $A_i = 0$이면 처음에 $i$번 칸에 블록이 없고, $A_i > 0$이면 처음에 $i$번 칸에 높이가 $A_i$인 블록이 있다.

미리 몇 개의 블록을 쓰러뜨릴 때, 시헌이가 게임을 클리어하기 위해 추가해야 하는 큐브 블록의 최소 개수를 출력한다.