시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 0 0 0 0.000%

문제

Za niz cijelih brojeva a1, a2, . . . , an kažemo da je sretan ako je svaki element niza (osim prvog i zadnjeg) jednak zbroju njemu susjednih elemenata: aj = aj−1 + aj+1.

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 a1, a2, . . . , an (−109 ≤ aj ≤ 109) — 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).