Harmonic sequence

A professor at a university in Flatland is running a lecture series on sequences. A sequence of integers $a_1, a_2, \ldots, a_n$ is called harmonic if every term except $a_1$ and $a_n$ equals the sum of its two neighbors: $a_2 = a_1 + a_3$, $a_3 = a_2 + a_4$, ..., $a_{n-1} = a_{n-2} + a_n$. For example, $[1, 2, 1, -1]$ is harmonic because $2 = 1 + 1$ and $1 = 2 + (-1)$.

For two sequences of equal length, $A = [a_1, \ldots, a_n]$ and $B = [b_1, \ldots, b_n]$, the distance is $d(A, B) = |a_1 - b_1| + |a_2 - b_2| + \ldots + |a_n - b_n|$. For example, $d([1, 2, 1, -1], [1, 2, 0, 0]) = 0 + 0 + 1 + 1 = 2$.

At the end of a lecture, the professor wrote a sequence of $n$ integers $B = [b_1, \ldots, b_n]$ on the board and assigned students the task of finding a harmonic sequence $A = [a_1, \ldots, a_n]$ with minimal $d(A, B)$. To make checking easy, the professor asks for only the minimal distance as the answer. Write a program that finds the minimal distance from $B$ to a harmonic sequence.

The first line contains an integer $n$, the number of elements in the sequence ($3 \le n \le 300\,000$).

The second line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($-10^9 \le b_i \le 10^9$).

Print one integer: the minimal possible distance from the sequence in the input to a harmonic sequence.

In the example, one optimal harmonic sequence is $[1, 2, 1, -1]$.