A series of lectures at the University of Flatland is devoted to the study of sequences.
The professor calls a sequence of integers
\(a_1, a_2, ..., a_n\) harmonious if every number except
\(a_1\) and
\(a_n\), equals the sum of adjacent:
\(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). For example, the sequence [1,2,1,–1] is harmonic because 2=1+1, and 1=2+(–1) .
Consider sequences of equal length:
\(A=[a_1,a_2, ... a_n]\) and
\(B=[b_1,b_2, ... b_n]\). The distance between these sequences will be called the value
\(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\) . For example,
\(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2| ++|1–0|+|–1–0|=0+0+1+1=2 \)
At the end of the lecture, the professor wrote on the blackboard a sequence of n integers
\(B=[b_1,b_2, ... b_n]\)and asked the students to find harmonious sequence
\(A=[a_1,a_2, ... a_n]\) such that
\(d( A, B)\) is minimal. To make it easier for himself to check, the professor asks you to write as an answer only the desired minimum distance
\(d(A,B)\) .
It is required to write a program that, given a sequence B, determines at what minimum distance from sequence B there is a harmonic sequence A.
Input
The first line of the input file contains the 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, …, b_n (–10^9 \le b_i \le 10^9 )\) .< br />
Imprint
The output file must contain a single integer: the minimum possible distance from the sequence in the input file to a harmonic sequence.
Examples
| # |
Input |
Output |
| 1 |
4
1 2 0 0
| 2 |