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.
- You can run across pillar in seconds and then climb up to pillar in additional seconds.
- 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 ?
Constraints
Subtask 1 [40%]
Subtask 2 [60%]
No additional constraints.
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
Comments