#dpa. [dp_a]Frog 1
[dp_a]Frog 1
Problem Statement
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 .
Constraints
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the minimum possible total cost incurred.
Sample Input 1
4
10 30 40 20
Sample Output 1
30
If we follow the path → → , the total cost incurred would be .
Sample Input 2
2
10 10
Sample Output 2
0
If we follow the path → , the total cost incurred would be .
Sample Input 3
6
30 10 60 10 60 50
Sample Output 3
40
If we follow the path → → → , the total cost incurred would be .