#P18826. [Croatian CPC2017] Sretan

[Croatian CPC2017] Sretan

[Croatian CPC2017] Sretan

题目描述

对于一个整数序列 a1,a2,…,ana_1,a_2,\ldots,a_n,如果除第一个和最后一个元素以外,每个元素都等于它两侧相邻元素之和,即

aj=aj−1+aj+1(2≤j≤n−1),a_j=a_{j-1}+a_{j+1}\qquad(2\le j\le n-1),

就称这个序列为幸运序列。

给定一个整数序列,每次操作可以选择一个元素,将它增加 11 或减少 11。求将给定序列变成幸运序列所需的最少操作次数。

输入格式

第一行包含一个整数 nn(3≤n≤3000003\le n\le300000)。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(−109≤aj≤109-10^9\le a_j\le10^9),表示初始序列。

输出格式

输出一个整数,表示最少操作次数。

样例 1

输入

4
5 1 -4 -5

输出

0

样例 2

输入

4
3 2 0 3

输出

6

样例说明

样例 2 可以用 66 次操作得到幸运序列 (2,2,0,−2)(2,2,0,-2)。