题目描述

译自 ROIR 2016 Day2 T4. Гармоничная последовательность

弗拉特兰大学的课程讲座专注于研究序列。教授将一个整数序列 $a_{1}, a_{2}, \ldots, a_{n}$ 定义为和谐序列，如果除了 $a_{1}$ 和 $a_{n}$ 之外，每个数字都等于其相邻两个数字之和，即：$a_{2}=a_{1}+a_{3}, a_{3}=a_{2}+a_{4}, \ldots, a_{n-1}=a_{n-2}+a_{n}$。例如，序列 $[1,2,1,-1]$ 是一个和谐序列，因为 $2=1+1$ 且 $1=2+(-1)$。

考虑两个长度相等的序列：$A=\left[a_{1}, a_{2}, \ldots, a_{n}\right]$ 和 $B=\left[b_{1}, b_{2}, \ldots, b_{n}\right]$。这两个序列之间的距离定义为 $d(A, B)=|a_{1}-b_{1}|+|a_{2}-b_{2}|+\ldots+|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$。

在讲座结束时，教授在黑板上写下了一个包含 $n$ 个整数的序列 $B=\left[b_{1}, b_{2}, \ldots, b_{n}\right]$，并要求学生们作为家庭作业，找到一个和谐序列 $A=\left[a_{1}, a_{2}, \ldots, a_{n}\right]$，使得 $d(A, B)$ 最小。为了方便检查，教授仅要求学生提交这个最小的距离 $d(A, B)$ 作为答案。

你需要编写一个程序，根据给定的序列 $B$，计算出距离序列 $B$ 最近的和谐序列 $A$，并输出这个最小距离。

输入格式

输入文件的第一行包含一个整数 $n$ $(3 \leq n \leq 300000)$，表示序列中元素的数量。

第二行包含 $n$ 个整数 $b_{1}, b_{2}, \ldots, b_{n}$ $(-10^{9} \leq b_{i} \leq 10^{9})$。

输出格式

输出文件应包含一个整数，即输入序列到某个和谐序列的最小可能距离。

4
1 2 0 0

2

在给出的样例中，最优的和谐序列例如为 $[1,2,1,-1]$，其与输入序列的距离为 $2$。

数据范围与提示

详细子任务附加限制及分值如下表所示：