Arithmetic Sequence Transformation

Time limit1sMemory limit512 MB

Summary

Each element of B can be changed by at most +1 or -1, and we want the cheapest way to make the whole sequence arithmetic.

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

Problem

A sequence $A = [A_1, A_2, \dots, A_N]$ of size $N$ is called arithmetic if $A_{i+1} - A_i$ is the same for every $1 \le i < N$ . For example, $[3]$ , $[6, 6, 6]$ , $[2, 8, 14, 20]$ , and $[6, 4, 2]$ are arithmetic, while $[4, 5, 4]$ and $[6, 3, 1]$ are not.

We want to transform the sequence $B = [B_1, B_2, \dots, B_N]$ into an arithmetic sequence. Each number can have an operation applied to it at most once. There are two operations: add 1 or subtract 1. Find the minimum number of operations needed to transform the sequence $B$ into an arithmetic sequence.

Input

The first line gives the size $N$ of the sequence $B$ $(1 \le N \le 10^5)$ . The second line gives $B_1, B_2, \dots, B_N$ $(1 \le B_i \le 10^9)$ .

Output

Print the minimum number of operations needed to transform the sequence $B$ into an arithmetic sequence. If it cannot be transformed into an arithmetic sequence, print -1.

Examples4

Example 1
Input
```
4
24 21 14 10
```
Expected output
```
3
```
Example 2
Input
```
2
5 5
```
Expected output
```
0
```
Example 3
Input
```
3
14 5 1
```
Expected output
```
-1
```
Example 4
Input
```
5
1 3 6 9 12
```
Expected output
```
1
```