포커 패

면접 대비

시간 제한1초메모리 제한128 MB

요약

각 랭크의 카드 수가 주어질 때, 각 랭크마다 정확히 그 수만큼 카드를 포함하는 연속 구간 스트레이트의 최소 개수를 구한다.

난이도: 보통10점 중 7점
유형: 그리디, 배열, 구현, 누적 합
정답자: 아직 제출이 없습니다

문제

Bessie와 친구들은 특별한 방식의 포커를 하고 있다. 이 게임의 덱에는 서로 다른 $N$ ( $1 \le N \le 100000$ )개의 숫자(랭크)가 있으며, $1$ 부터 $N$ 까지 번호가 매겨져 있다(보통의 덱은 $N = 13$ 이다).

이 게임에서 소들이 낼 수 있는 패는 단 한 종류뿐이다. $i \le j$ 인 두 랭크 $i$ 와 $j$ 를 고른 뒤, $i$ 부터 $j$ 까지의 모든 랭크에 대해 카드를 정확히 한 장씩 내는 것이다. 이러한 패를 '스트레이트(straight)'라고 부른다.

Bessie는 현재 랭크 $i$ 의 카드를 $a_i$ 장 ( $0 \le a_i \le 100000$ ) 들고 있다. 가지고 있는 카드를 모두 없애기 위해 Bessie가 내야 하는 스트레이트의 최소 개수를 구하여라.

입력

첫째 줄에 정수 $N$ 이 주어진다.
이어지는 $N$ 개의 줄 중 $i+1$ 번째 줄에는 랭크 $i$ 의 카드 수 $a_i$ 가 주어진다.

출력

Bessie가 모든 카드를 없애기 위해 내야 하는 스트레이트의 최소 개수를 한 줄에 출력한다.

힌트

예제의 경우, Bessie는 다음과 같이 카드를 낼 수 있다: $1$ 부터 $5$ 까지의 스트레이트, $1$ 부터 $2$ 까지의 스트레이트, $4$ 부터 $5$ 까지의 스트레이트, $2$ 부터 $2$ 까지의 스트레이트 두 번, 그리고 $5$ 부터 $5$ 까지의 스트레이트. 이렇게 하면 총 6번 만에 모든 카드를 없앨 수 있다.

예제3

예제 1
입력
```
5
2
4
1
2
3
```
예상 출력
```
6
```
예제 2
입력
```
1
5
```
예상 출력
```
5
```
예제 3
입력
```
5
1
2
3
4
5
```
예상 출력
```
5
```