题目背景

翻译自 ROIR 2016 D2T4。

题目描述

如果一个整数数列 $a_1, a_2, \dots, a_n$ 满足其中每个数（除了 $a_1$ 和 $a_n$）等于其相邻两个数的和，即 $a_2 = a_1 + a_3, a_3 = a_2 + a_4, \dots, a_{n-1} = a_{n-2} + a_n$，那么我们称这个序列为和谐数列。

例如，数列 $[1, 2, 1, {-1}]$ 是和谐数列，因为 $2 = 1 + 1$，且 $1 = 2 + ({-1})$。

现在考虑两个相同长度的数列 $A = [a_1, a_2, \dots, a_n]$ 和 $B = [b_1, b_2, \dots, b_n]$。我们定义它们之间的距离为：

$$d(A, B) = |a_1 - b_1| + |a_2 - b_2| + \dots + |a_n - b_n| $$

例如，$d([1, 2, 1, {-1}], [1, 2, 0, 0]) = |1 - 1| + |2 - 2| + |1 - 0| + |{-1} - 0| = 0 + 0 + 1 + 1 = 2$。

现有一个数列 $B = [b_1, b_2, \dots, b_n]$，需要找出一个和谐数列 $A = [a_1, a_2, \dots, a_n]$，使得 $d(A, B)$ 最小。你只需要求出 $d(A, B)$ 的最小值即可。

输入格式

第一行输入一个整数 $n$，表示数列的长度（$3 \leq n \leq 300000$）。

第二行输入 $n$ 个整数 $b_1,b_2,\dots,b_n$（$-10^9 \leq b_i \leq 10^9$）。

输出格式

输出一个整数，表示 $d(A, B)$ 的最小值。

4  
1 2 0 0

2

提示

样例解释

在样例中，可以令 $A=[1, 2, 1, {-1}]$，这样 $d([1, 2, 1, {-1}], [1, 2, 0, 0]) = 2$。可以证明 $d(A,B)$ 不可能小于 $2$。

数据范围

子任务	是否捆绑	分值	$3\le n\le$	$\lvert b_i\rvert\le$
$1$	是	$14$	$3$	$10$
$2$			$500$	$100$
$3$		$16$	$100000$
$4$			$1000$	$10^9$
$5$		$40$	$300000$