## Educational DP Contest AtCoder A - Frog 1

View as PDF

Points: 7
Time limit: 1.0s
Memory limit: 1G

Problem type

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 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 .