C. Progression
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a set of $$$n$$$ integers. Determine the minimum number of integers that must be added to this set so that all numbers can be arranged into an arithmetic progression.

Explanation: a sequence of numbers forms an arithmetic progression if all differences between adjacent elements are equal.

Input

The first line contains an integer $$$n$$$ — the number of numbers ($$$1 \le n \le 10^5$$$). The next $$$n$$$ lines contain integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).

Output

Print one integer — the minimum number of integers that must be added to the input set. If there is no solution, print -1.

Example
Input
3
-2
7
1
Output
1
Note

In the example, you can add the number 4, then the sequence -2 1 4 7 forms an arithmetic progression.