이삿짐 상자

당신은 방금 친구의 이사를 도왔지만, 안타깝게도 이삿짐 상자로 가득 찬 좁은 복도의 잘못된 쪽 끝에 갇혔다. 복도는 이삿짐 상자 더미 $N$개로 이루어져 있으며, $i$번 더미에는 상자가 $a_i$개 있다. 모든 상자의 크기는 같다.

밖으로 나가는 유일한 방법은 $1$번 더미부터 $N$번 더미까지 더미 위를 걸어가는 것이다. 어떤 더미 위에 있을 때 인접한 더미로 이동할 수 있지만, 그 더미가 현재 서 있는 더미보다 높지 않은 경우에만 가능하다. 현재 서 있는 더미가 인접한 더미보다 상자 두 개 이상 더 높다면, 현재 서 있는 더미의 맨 위 상자를 그 인접한 더미로 밀어 떨어뜨릴 수도 있다. 이 동작은 원하는 만큼 반복할 수 있다.

현재 당신은 $1$번 더미 위에 있다. 안타깝게도 $N$번 더미에 도달하는 것이 불가능할 수도 있다. 하지만 다행히 걷기 시작하기 전에 $1$번 더미에 원하는 수만큼 추가 상자를 놓을 수 있다. $N$번 더미에 도달하기 위해 추가해야 하는 상자의 수를 계산하는 프로그램을 작성하라.

그림은 예제 1를 보여 준다. 짙은 회색 상자는 추가 상자이다. 따라서 전략은 맨 위의 추가 상자를 2번 더미로 밀어 떨어뜨리는 것이다. 그러고 나면 4번 더미까지 곧장 걸어갈 수 있다. 3개보다 적은 추가 상자로는 불가능했을 것이다.

점수

다음 조건을 만족하는 테스트 케이스에는

$20$점 | 조건 |$N=3$| , $1 \le a_i \le 20$.

$20$점 | |$3\le N\le 5$| , $1 \le a_i \le 100$.

$20$점 | |$5\le N\le 10$| , $1 \le a_i \le 1000$.

$40$점 | |$10\le N\le 20$| , $1 \le a_i \le 3000$.

첫째 줄에 더미의 수를 나타내는 정수 $N$이 주어진다. 둘째 줄에 각 더미에 있는 상자의 수를 나타내는 $N$개의 정수 $a_i$가 주어진다.

추가해야 하는 이삿짐 상자의 최소 개수를 나타내는 정수 하나를 출력한다.