favorite We need a little bit of your help to keep things running, click on this banner to learn more

Dynamic Programming - Linear


There are n stones, numbered 1, 2, ..., n. For each i (1in), the height of stone i is hi. There is a frog who is initially on stone 1. It will repeat the following action some number of times to reach stone n: if the frog is currently on stone i, jump to stone i + 1 or stone i + 2. Here, a cost of |hihj| is incurred, where j is the stone to land on.

Find the minimum possible total cost incurred before the frog reaches stone n.


First line contains number n (2n105). Second line contains integers h1, h2, ..., hn (1hi104).


Print the minimum possible total cost for frog to reach stone n.

Time limit 1 second
Memory limit 128 MiB
Input example #1
10 30 40 20
Output example #1