Problem: The Treeless Trees

Want to try solving this problem? You can submit your code online if you log in or register.

The Treeless Trees

Time Limit: 1 second
Memory Limit: 128 MB
Input: stdin
Output: stdout

The autumn is silence and wind. A bitter morning sees Seiko and her katana (sword) teacher travelling through the old forest. The latter stops to point out a line of bamboo trees of varying heights, some of them many metres tall.

He says:

"Any novice can slice a target apart with a blade and sheer strength. A master, though, is above such brute force. To dismantle without losing a single bead of sweat: that is the way of a master.

First, take your sword and choose a height. Then, choose a consecutive range of trees that are at least of that height. With the right technique, you can jump and slice through those trees-"

$\includegraphics[scale=0.3]{bamboo2}$

"-so that their heights are all reduced by your chosen height.

Now! Continue in this way until you have reduced all these trees to stumps¹."

The technique for reducing ranges of trees is not impossible, but nor is it easy. The higher Seiko jumps, the more energy the technique requires.

Meditating on this, Seiko realises that her task now is to conserve her energy (and so find the smallest total jump height required).

Input

The first line of input will contain the integer N, the number of bamboo trees. The following N lines will each contain a single integer, representing the height of that tree (in metres).

Output

Output should consist of a single integer: the smallest-possible total jump height (in metres) it will take Seiko to reduce all the trees to zero height.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Explanation

The first sample case corresponds to the illustration above. One possible sequence of jumps to reduce all heights to zero would be:

Jump 2 metres and cut trees 2 to 4 (as illustrated)
Jump 1 metre and cut trees 3 to 4 (leaving trees of height 1, 1, 2, 1, 1, 2)
Jump 1 metre and cut trees 1 to 6 (leaving trees of height 0, 0, 1, 0, 0, 1)
Jump 1 metre and cut tree 3 (leaving trees of heights 0, 0, 0, 0, 0, 1)
Jump 1 metre and cut tree 6 (leaving trees of heights 0, 0, 0, 0, 0, 0)

The total jump height would be 2+1+1+1+1=6.

In the second sample case, Seiko can cut down all three trees in one huge jump of height 1,000,000.

Subtasks & Constraints

For all subtasks, 1 ≤ N ≤ 100,000 and each tree will have a (integer) height between 1 and 1,000,000 inclusive.

For Subtask 1 (10 points), N = 3.
For Subtask 2 (40 points), 1 ≤ N ≤ 500.
For Subtask 3 (50 points), no further constraints apply.