Educational DP Contest AtCoder A - Frog 1
View as PDFThere 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 Specification
The first line of input will contain an integer .
The second line of input will contain  spaced integers, 
, the height of stone 
.
Output Specification
Output a single integer, the minimum possible total cost incurred.
Sample Input 1
4
10 30 40 20
Sample Output 1
30
Sample Input 2
2
10 10
Sample Output 2
0
Sample Input 3
6
30 10 60 10 60 50
Sample Output 3
40
Sample Explanations
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 
.
Comments