Državno natjecanje iz informatike 2017. / Srednja škola / Druga podskupina (3. i 4. razred) – drugi dan natjecanja

Mali Mislav svakog jutra posjećuje sve lopoče na mirnom rukavcu rijeke Save u blizini njegovog grada.

Duž rukavca raste n lopoča označenih brojevima od 1 do n slijeva na desno.

Mislav želi posjetiti sve lopoče u nekom redoslijedu, veselo skačući s lopoča na lopoč tako da svaki lopoč posjeti točno jednom.

Početni i završni lopoč na svom putu može proizvoljno odabrati.

Lopoč j je visine hj milimetara.

Budući da se Mislav boji visine on nikad neće skočiti sa višeg lopoča na niži.

Dakle, prilikom obilaska Mislav uvijek skače na lopoč veće ili jednake visine kao onaj na kojem se trenutno nalazi.

Mislav može skočiti koliko daleko želi.

Međutim, za skok od lopoča a do lopoča b on potroši |a−b| kalorija energije.

Pronađite najmanji mogući broj kalorija potreban da Mislav obiđe sve lopoče.

Ulazni​ podaci

U prvom redu nalazi se prirodni broj n (1 ≤ n ≤ 500 000) — broj lopoča.

U sljedećem redu nalazi se prirodni brojevi h1, h2, . . . , hn (1 ≤ hj ≤ 500 000) — visine lopoča slijeva na desno.

Izlazni podaci

Ispišite jedan broj — traženi najmanji mogući broj kalorija.

Primjeri test​ podataka

Ulaz

4
2 1 3 2

Izlaz

5

Objašnjenje

Pojašnjenje prvog primjera: Jedan optimalan redoslijed skokova je 2 – 1 – 4 – 3.

Ulaz

7
3 3 2 1 2 1 2

Izlaz

9