타이어 홈 깎기

구미구미 공장은 타이어를 만든다. 이 공장의 홈 깎는 기계가 타이어에 홈을 새긴다.

타이어에는 세로 홈이 $N$개 있고, 이 홈이 고무를 $N+1$개의 세로 구역으로 나눈다. 각 세로 구역에는 가로로 홈을 새겨서 그 구역을 크기가 모두 같은 조각으로 나눈다.

기계는 한 번 절단할 때 세로 구역 하나 이상에 동시에 홈을 새길 수 있고, 그 구역들이 서로 붙어 있지 않아도 된다. 대신 절단은 직선으로만 할 수 있으므로, 한 번의 절단에 함께 들어가는 구역은 모두 같은 높이에서 잘린다.

세 번째 예제에 해당하는 절단 방법이다.

그림에서 가장 위와 가장 아래의 가로선은 타이어를 가로지르는 경계선이고, 맨 왼쪽과 맨 오른쪽의 세로선은 타이어의 양 끝이다. 이 경계선과 이미 나 있는 세로 홈은 절단 횟수에 세지 않는다.

타이어의 모양이 주어진다. 이 모양을 만드는 데 필요한 가로 절단의 최소 횟수를 구하라.

첫째 줄에 정수 $N$이 주어진다. ($1 \le N \le 100\,000$)

이어지는 $N+1$개의 줄에 정수 $a_i$가 한 줄에 하나씩 주어진다. ($1 \le a_i \le 100\,000$) $a_i$는 $i$번째 세로 구역이 몇 조각으로 나뉘어야 하는지를 나타낸다.

첫째 줄에 필요한 가로 절단의 최소 횟수를 출력한다.