Ancient Castle Ruins

View as PDF

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

You stumble across the ruins of an ancient castle...

The ruins of the castle have left a strange pillar formation behind. In particular, there are adjacent pillars each with height . Let represent your exhaustion. It initially starts at , and increases by after each time you jump to a taller pillar. It takes seconds to travel from pillar to pillar if . However, there are different ways to travel to a taller pillar.

1. You can run across pillar in seconds and then climb up to pillar in additional seconds.
2. You can jump directly from pillar to pillar in seconds. You can jump as high as you want, but jumping will exhaust you.

Given this information, what is the lowest amount of time needed to get from pillar to pillar ?

Input Specification

The first line of input contains an integer .

The second line of input contains space separated integers representing , the height of each pillar.

Output Specification

Output a single integer, the lowest achievable time in seconds.

Sample Input

9
6 2 1 2 3 9 2 3 7

Sample Output

14