Za niz cijelih brojeva a₁, a₂, . . . , a_n kažemo da je sretan ako je svaki element niza (osim prvog i zadnjeg) jednak zbroju njemu susjednih elemenata: a_j = a_j−1 + a_j+1.</p>

Zadan je niz cijelih brojeva, u svakom koraku možemo odabrati jedan element niza te ga povećati ili smanjiti za jedan. Odredite minimalan broj koraka potreban da dobijemo sretan niz.

입력 형식

U prvom redu se nalazi prirodni broj n (3 ≤ n ≤ 300 000) — broj elemenata niza. Sljedeći red sadrži n cijelih brojeva a₁, a₂, . . . , a_n (−10⁹ ≤ a_j ≤ 10⁹) — zadani niz.

출력 형식

Ispišite traženi minimalni broj koraka.

예제 입력 1

4
5 1 -4 -5

예제 출력 1

0

예제 입력 2

4
3 2 0 3

예제 출력 2

6

힌트

U drugom primjeru test podataka, sa 6 koraka možemo doći do sretnog niza (2 2 0 -2).