Bessie Poker Straight Hands

Bessie and her friends are playing a unique version of poker with a deck that has \(N\) (\(1 \le N \le 100000\)) different ranks, numbered from 1 to \(N\) (a normal deck has \(N = 13\)). In this game, there is only one type of hand: a straight. A straight is defined by choosing two ranks, \(i\) and \(j\) (with \(i \le j\)), and playing one card of each rank from \(i\) to \(j\), inclusive.

Bessie currently holds \(a_i\) cards of rank \(i\) (\(0 \le a_i \le 100000\)). Her goal is to play a sequence of straights so that all cards in her hand are used. Find the minimum number of straights she must play to achieve this.

Hint: One optimal strategy is to realize that the minimum number of straights needed is given by:

[ a_1 + \sum_{i=2}^{N} \max(0, a_i - a_{i-1}) ]

This is because Bessie must start at least \(a_1\) straights at rank 1, and for each rank \(i\) (\(i \ge 2\)) if \(a_i\) exceeds \(a_{i-1}\), additional straights are needed starting at rank \(i\).

inputFormat

The first line contains an integer \(N\) (the number of ranks). The second line contains \(N\) space-separated integers \(a_1, a_2, \dots, a_N\), where \(a_i\) represents the number of cards of rank \(i\).

outputFormat

Output a single integer -- the minimum number of straight hands needed to discard all cards.

sample

1
5

5