25499번 - Tipover Transform

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

• 보드판은 $(N + 1)$개의 칸이 일렬로 나열된 구조로 되어 있다. 각각의 칸은 가로와 세로가 $1\text{ cm}$인 정사각형 모양이며 왼쪽부터 차례로 $0 \sim N$의 번호를 받는다.
• 각각의 칸에는 블록이 최대 한 개 놓일 수 있다. 모든 블록은 처음에 세워져 있으며, 세워진 블록은 가로와 세로가 각각 $1\text{ cm}$이고 높이는 $2\text{ cm}$ 이상인 직육면체 모양을 하고 있다. 각 블록의 높이는 $1\text{ cm}$의 정수 배이다.
• 세워진 블록은 왼쪽이나 오른쪽으로 쓰러뜨릴 수 있다. $i$번 칸에 높이가 $k \text{ cm}$인 블록이 있을 때, 이것을 왼쪽으로 쓰러뜨리면 이 블록은 $(i-k) \sim (i-1)$번째 칸을 덮게 되고, 오른쪽으로 쓰러뜨리면 $(i+1) \sim (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$인 블록이 존재하는 것이다.

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