There are stones, numbered . For each , the height of Stone is .
There is a frog who is initially on Stone . He will repeat the following action some number of times to reach Stone :
- If the frog is currently on Stone , jump to Stone or Stone . Here, a cost of is incurred, where is the stone to land on.
Find the minimum possible total cost incurred before the frog reaches Stone .
- All values in input are integers.
The first line of input will contain an integer .
The second line of input will contain spaced integers, , the height of stone .
Output a single integer, the minimum possible total cost incurred.
Sample Input 1
4 10 30 40 20
Sample Output 1
Sample Input 2
2 10 10
Sample Output 2
Sample Input 3
6 30 10 60 10 60 50
Sample Output 3
For the first sample, we can follow path , the total cost incurred would be .
For the second sample, we can follow the path , with the total cost incurred being .
In the last sample, we follow the path , the total cost incurred would be .