I found an interesting problem on https://codeforces.com/problemset/problem/978/D:
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$.


-----Input-----

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


-----Output-----

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


-----Examples-----
Input
4
24 21 14 10

Output
3

Input
2
500 500

Output
0

Input
3
14 5 1

Output
-1

Input
5
1 3 6 9 12

Output
1



-----Note-----

In the first example Polycarp should increase the first number on $1$, decrease the second number on $1$, increase the third number on $1$, and the fourth number should left unchanged. So, after Polycarp changed three elements by one, his sequence became equals to $[25, 20, 15, 10]$,...

I tried it in Python, but could not do it. Can you solve it?
def solve(n, a):
	if n <= 2:
		return 0

	d = [v - u for u, v in zip(a, a[1:])]

	max_d = max(d)
	min_d = min(d)
	if max_d - min_d > 4:
		return -1

	min_cnt = -1
	for d in range(min_d, max_d + 1):
		for d0 in range(-1, 2):
			y = a[0] + d0
			valid = True
			cnt = 0 if d0 == 0 else 1
			for x in a[1:]:
				dx = abs(y + d - x)
				if dx > 1:
					valid = False
					break

				cnt += dx
				y += d
			if valid:
				# print(d)
				if cnt < min_cnt or min_cnt < 0:
					min_cnt = cnt
	return min_cnt

def main():
	n = int(input())
	a = [int(_) for _ in input().split()]

	ans = solve(n, a)
	print(ans)

def __starting_point():
	main()

__starting_point()