Happy Sequence

Interview

Time limit3sMemory limit512 MB

Summary

Change a sequence with unit-cost edits so every interior term equals the sum of its two neighbours, minimizing total edits.

Level: Medium6 of 10
Topics: Math, Implementation, Greedy, Brute force
Solved: No attempts yet

Problem

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.

Input

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$ )

Output

Print the minimum number of steps.

Note

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

Examples2

Example 1
Input
```
4
5 1 -4 -5
```
Expected output
```
0
```
Example 2
Input
```
4
3 2 0 3
```
Expected output
```
6
```