Frog Hops

Difficulty: 1200 3000 ms 128 MB

dp

A frog starts on stone 1 and must reach stone N, jumping to the next stone or skipping one. Jumping from height a to height b costs |a − b|. Minimize the total cost.

Input: the first line has N; the second line has the N stone heights.

Output: the minimum total cost.

Constraints:

• 1 ≤ N ≤ 10⁵
• 0 ≤ h_i ≤ 10⁴

Sample Tests

4
10 30 40 20

30

2
10 10

0

Read the Editorial