A11675 | Almost Arithmetic Progression

Polycarp likes arithmetic progressions. A sequence $[a_1, a_2, \dots, a_n]$ is called an arithmetic progression if for each $i$ ( $1 \le i < n$ ) the value $a_{i+1} - a_i$ is the same. For example, the sequences $[42]$ , $[5, 5, 5]$ , $[2, 11, 20, 29]$ and $[3, 2, 1, 0]$ are arithmetic progressions, but $[1, 0, 1]$ , $[1, 3, 9]$ and $[2, 3, 1]$ are not.

It follows from the definition that any sequence of length one or two is an arithmetic progression.

Polycarp found some sequence of positive integers $[b_1, b_2, \dots, b_n]$ . He agrees to change each element by at most one. In the other words, for each element there are exactly three options: an element can be decreased by $1$ , an element can be increased by $1$ , an element can be left unchanged.

Determine a minimum possible number of elements in $b$ which can be changed (by exactly one), so that the sequence $b$ becomes an arithmetic progression, or report that it is impossible.

It is possible that the resulting sequence contains element equals $0$ .

The first line contains a single integer $n$ $(1 \le n \le 100\,000)$ — the number of elements in $b$ .

The second line contains a sequence $b_1, b_2, \dots, b_n$ $(1 \le b_i \le 10^{9})$ .

If it is impossible to make an arithmetic progression with described operations, print -1. In the other case, print non-negative integer — the minimum number of elements to change to make the given sequence becomes an arithmetic progression. The only allowed operation is to add/to subtract one from an element (can't use operation twice to the same position).