Poker Hands

Interview

Time limit1sMemory limit128 MB

Summary

Given card counts per rank, find the fewest contiguous-rank straights whose unit cards sum to exactly those counts.

Level: Medium7 of 10
Topics: Greedy, Array, Implementation, Prefix sum
Solved: No attempts yet

Problem

Bessie and her friends are playing a special version of poker. The deck has $N$ ( $1 \le N \le 100000$ ) distinct ranks, numbered $1$ through $N$ (an ordinary deck has $N = 13$ ).

In this game there is exactly one kind of hand a cow may play: choose two ranks $i$ and $j$ with $i \le j$ , then play exactly one card of every rank from $i$ to $j$ inclusive. Such a hand is called a straight.

Bessie currently holds $a_i$ cards of rank $i$ ( $0 \le a_i \le 100000$ ). Find the minimum number of straights she must play to get rid of all of her cards.

Input

The first line contains the integer $N$ .
Among the next $N$ lines, the $(i+1)$ -th line contains $a_i$ , the number of cards of rank $i$ .

Output

Print a single integer: the minimum number of straights Bessie must play to get rid of all of her cards.

Hint

For the sample case, Bessie can play a straight from $1$ to $5$ , a straight from $1$ to $2$ , a straight from $4$ to $5$ , two straights from $2$ to $2$ , and a straight from $5$ to $5$ , for a total of 6 hands needed to discard all of her cards.

Examples3

Example 1
Input
```
5
2
4
1
2
3
```
Expected output
```
6
```
Example 2
Input
```
1
5
```
Expected output
```
5
```
Example 3
Input
```
5
1
2
3
4
5
```
Expected output
```
5
```