조화 수열

Flatland 대학교에서는 수열을 주제로 한 강의가 열린다. 정수로 이루어진 수열 $a_1, a_2, \ldots, a_n$은 $a_1$과 $a_n$을 제외한 모든 항이 양옆 이웃한 두 항의 합과 같으면 조화 수열이라고 부른다. 즉 $a_2 = a_1 + a_3$, $a_3 = a_2 + a_4$, ..., $a_{n-1} = a_{n-2} + a_n$이 성립한다. 예를 들어 $[1, 2, 1, -1]$은 $2 = 1 + 1$이고 $1 = 2 + (-1)$이므로 조화 수열이다.

길이가 같은 두 수열 $A = [a_1, \ldots, a_n]$과 $B = [b_1, \ldots, b_n]$의 거리는 $d(A, B) = |a_1 - b_1| + |a_2 - b_2| + \ldots + |a_n - b_n|$로 정의한다. 예를 들어 $d([1, 2, 1, -1], [1, 2, 0, 0]) = 0 + 0 + 1 + 1 = 2$이다.

교수는 강의가 끝날 때 길이 $n$의 정수 수열 $B = [b_1, \ldots, b_n]$을 칠판에 적고, $d(A, B)$가 최소가 되는 조화 수열 $A = [a_1, \ldots, a_n]$을 찾아오라는 과제를 냈다. 채점을 쉽게 하려고 답으로는 최소 거리만 쓰게 했다. 주어진 $B$에서 조화 수열까지의 최소 거리를 구하는 프로그램을 작성하라.

첫째 줄에 수열의 원소 개수 $n$이 주어진다 ($3 \le n \le 300\,000$).

둘째 줄에 정수 $b_1, b_2, \ldots, b_n$이 주어진다 ($-10^9 \le b_i \le 10^9$).

입력된 수열에서 조화 수열까지의 최소 거리를 정수 하나로 출력한다.

예시에서 최적의 조화 수열은 예를 들어 $[1, 2, 1, -1]$이다.