Poker Hands

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.

• 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$.

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

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.