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

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-"

"-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^{1}."

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).

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

6 1 3 5 4 1 2

6

3 1000000 1000000 1000000

1000000

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)

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

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.

Privacy
statement

© Australian Mathematics Trust 2001-2022

Page generated: 25 September 2022, 1:38am AEST