e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Dynamic Programming - Linear

Лягушка

Имеются n камней, пронумерованных 1, 2, ..., n. Для каждого i (1in) высота i -го камня равна hi. Лягушка изначально находится на камне 1. Она повторяет следующее действие некоторое количество раз для достижения камня n: если лягушка находится на камне i, то она может прыгнуть или на камень i + 1 или на камень i + 2. Стоимость перемещения с i-го на j-ый камень равна |hihj|.

Найдите наименьшую стоимость перемещения лягушки на камень n.

Входные данные

Первая строка содержит количество камней n (2n105). Вторая строка содержит целые числа h1, h2, ..., hn (1hi104).

Выходные данные

Выведите наименьшую стоимость перемещения лягушки на камень n.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4
10 30 40 20
Вихідні дані #1
30