Problem
Una serie de conferencias en la Universidad de Flatland está dedicada al estudio de las secuencias.
El profesor llama armoniosa a una secuencia de enteros
\(a_1, a_2, ..., a_n\) si todos los números excepto
\(a_1\) y
\(a_n\), es igual a la suma de los adyacentes:
\(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). Por ejemplo, la secuencia [1,2,1,–1] es armónica porque 2=1+1 y 1=2+(–1) .
Considere secuencias de igual longitud:
\(A=[a_1,a_2, ... a_n]\) y
\(B=[b_1,b_2, ... b_n]\). La distancia entre estas secuencias se llamará valor
\(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n |\) . Por ejemplo,
\(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2 | +|1–0|+|–1–0|=0+0+1+1=2 \)
Al final de la lección, el profesor escribió en la pizarra una secuencia de n enteros
\(B=[b_1,b_2, ... b_n]\)y preguntó los estudiantes encuentren una secuencia armoniosa
\(A=[a_1,a_2, ... a_n]\) tal que
\( d( A, B)\) es mínimo. Para que le resulte más fácil comprobarlo, el profesor le pide que escriba como respuesta solo la distancia mínima deseada
\(d(A,B)\) .
Se requiere escribir un programa que, dada una secuencia B, determine a qué distancia mínima de la secuencia B existe una secuencia armónica A.
Entrada
La primera línea del archivo de entrada contiene el número entero n – el número de elementos en la secuencia (
\(3 \le n \le 500\)).
La segunda línea contiene n enteros
\(b_1, b_2, …, b_n (–100 \le b_i \le 100 )\) .
Impresión
El archivo de salida debe contener un solo número entero: la distancia mínima posible desde la secuencia en el archivo de entrada a una secuencia armónica.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
4
1 2 0 0
| 2 |