Module: Linear enumeration


Problem

4 /5


Harmonious sequence lite

Problem

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 500\)).

The second line contains n integers \(b_1, b_2, …, b_n (–100 \le b_i \le 100 )\) .

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