Happy Sequence

A sequence of integers $a_1, a_2, \dots, a_n$ is called happy if every element except the first and the last one equals the sum of its two neighbours, that is, $a_j = a_{j-1} + a_{j+1}$ for every $j$ with $2 \le j \le n-1$.

You are given a sequence of integers. In one step you can choose one element of the sequence and increase or decrease it by one. Find the minimum number of steps needed to obtain a happy sequence.

The first line contains a positive integer $n$, the length of the sequence. ($3 \le n \le 300\,000$)

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ separated by spaces. ($-10^9 \le a_j \le 10^9$)

Print the minimum number of steps.

In the second example, 6 steps are enough to reach the happy sequence $(2, 2, 0, -2)$.