Minimizing Distance to a Harmonious Sequence

We call an integer sequence (a_1, a_2, \dots, a_n) a harmonious sequence if every element (except the first and last) equals the sum of its two neighbors. In other words, the sequence satisfies [ a_2 = a_1 + a_3,\quad a_3 = a_2 + a_4,\quad \dots,\quad a_{n-1} = a_{n-2} + a_n. ] For example, the sequence ([1, 2, 1, -1]) is harmonious because (2 = 1 + 1) and (1 = 2 + (-1)).

Given a sequence (B = [b_1, b_2, \dots, b_n]), we define the distance between a candidate harmonious sequence (A = [a_1, a_2, \dots, a_n]) and (B) as [ d(A, B) = |a_1 - b_1| + |a_2 - b_2| + \dots + |a_n - b_n|. ] Your task is to choose a harmonious sequence (A) so that (d(A, B)) is minimized, and output the minimum possible distance.

Note: Any harmonious sequence (A) is uniquely determined by its first two elements. In fact, if we let (a_1 = x) and (a_2 = y), then for (i \ge 3) the recurrence [ a_i = a_{i-1} - a_{i-2} ] holds. This generates a periodic pattern with period 6: [ a_1 = x,\quad a_2 = y,\quad a_3 = y-x,\quad a_4 = -x,\quad a_5 = -y,\quad a_6 = x-y,\quad a_7 = x,\quad \dots ]

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 100), the length of the sequence \(B\).

The second line contains n space-separated integers \(b_1, b_2, \dots, b_n\) where each \(|b_i| \le 10^4\).

outputFormat

Output a single integer: the minimum possible distance \(d(A, B)\) between a harmonious sequence \(A\) and the given sequence \(B\).

sample

4
1 2 1 -1

0