There are n points on a straight line, and the i-th point among them is located at x_{i}. All these coordinates are distinct.

Determine the number m — the smallest number of points you should add on the line to make the distances between all neighboring points equal. 


-----Input-----

The first line contains a single integer n (3 ≤ n ≤ 100 000) — the number of points.

The second line contains a sequence of integers x_1, x_2, ..., x_{n} ( - 10^9 ≤ x_{i} ≤ 10^9) — the coordinates of the points. All these coordinates are distinct. The points can be given in an arbitrary order.


-----Output-----

Print a single integer m — the smallest number of points you should add on the line to make the distances between all neighboring points equal. 


-----Examples-----
Input
3
-5 10 5

Output
1

Input
6
100 200 400 300 600 500

Output
0

Input
4
10 9 0 -1

Output
8



-----Note-----

In the first example you can add one point with coordinate 0.

In the second example the distances between all neighboring points are already equal, so you shouldn't add anything.

Difficulty: interview

Starter code:

Solutions:
def gcd(a, b):
    if(a==0):
        return b
    return gcd(b%a, a)    

n=int(input())
v=list(map(int,input().split()))
v.sort()
ans=v[1]-v[0]
for i in range(2, n):
    ans=gcd(ans, v[i]-v[i-1])
print((v[len(v)-1]-v[0])//ans+1-n) 

def gcd(a, b):
    a = int(a)
    b = int(b)
    if b == 0:
        return a
    return gcd(b, a % b)
n = int(input())
a = input().split()
for i in range(0, n):
    a[i] = int(a[i])
a = sorted(a)
d = 0
for i in range(1, n):
    d = gcd(d, a[i] - a[i - 1])
print(int((a[n-1] - a[0]) / d - n + 1))

def lcm(a, b):
    m = a*b
    while a != 0 and b != 0:
        if a > b:
            a %= b
        else:
            b %= a
    return a+b


n = int(input())
s = input()
points = [int(i) for i in s.split()]
points = sorted(points)

dist = []

for i in range(len(points) - 1):
    dist.append(points[i + 1] - points[i])


c = dist[0]
for i in range(1, len(dist)):
    c = lcm(c, dist[i])

ans = 0
for i in range(len(dist)):
    ans += dist[i] // c - 1

print(int(ans))




from fractions import gcd
from functools import reduce

n = int(input())
x = list(map(int, input().split()))
x.sort()

difs = []
for i in range(len(x)-1):
  difs.append(x[i+1]-x[i])

dif = reduce(gcd, difs)

mmin = x[0]
mmax = x[-1]
x = set(x)
cnt = (mmax-mmin+dif)//dif-n
print(cnt)


def gcd(a,b):
	if a==0:
		return b
	while b:
		a%=b
		[a,b]=[b,a]
	return a

n=int(input())
a=[int(x) for x in input().split()]
a.sort()
tek=0
res=0
for x in a:
	if x!=a[0]:
		res=gcd(res,x-tek)
	tek=x
print((tek-a[0])//res-n+1)

n = int(input())

m = list(map(int, input().split()))

m.sort()

min_dif = m[1] - m[0] 

def nod(a, b):
    if b == 0:
        return a
    else:
        return nod(b, a %b)

for i in range(1, n):
    min_dif = nod(min_dif, m[i] - m[i-1])

ans = 0

for i in range(1, n):
    if m[i] - m[i-1] > min_dif:
        ans += (m[i] - m[i-1]) / min_dif - 1

print(int(ans))


n = int(input())
a = sorted([int(x) for x in input().split()])


def mcd(a, b):
    while a != 0 and b != 0:
        if a > b:
            a = a % b
        else:
            b = b % a
    return a + b

min_ = mcd(a[1] - a[0], a[2] - a[1])
for i in range(3, n):
    min_ = mcd(min_, a[i] - a[i - 1])
    if min_ == 1:
        break
# if min_ == 1:
#     print(a[-1] - a[0] - n + 2)
# else:
count = 0

for i in range(1, n):
    count += (a[i] - a[i - 1]) // min_ - 1

print(count)



from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
a.sort()
for i in range(1, len(a)):
    a[i-1] = a[i] - a[i-1]
a.pop()
g = a[0]
s = 0
for i in range(len(a)):
    s += a[i]
    g = gcd(g, a[i])
s = s // g - len(a)
print(s)

def gcd(a, b):

	while a != 0 and b != 0:

		if b > a:
	
			b = b % a
	
		else:

			a = a % b

	if a == 0:

		return b

	else:
		
		return a


n = int(input())

a = input()

a = a.split()

for i in range(len(a)):
	
	a[i] = int(a[i])

a = sorted(a)

b = a[1] - a[0]

for i in range(0, len(a) - 1):
	
	b = gcd(b, a[i + 1] - a[i])

cnt = (a[len(a) - 1] - a[0]) // b + 1

print(cnt - n)

def f(a, b):
    while a and b:
        if (a<b):
            b = b%a
        else :
            a = a%b
    return a+b;
    

    
n = int(input())

List = []
for i in range(n):
    List.append(0)

i = 0
for s in input().split(' '):
     List[i] = int(s)
     i = i+1
    
List.sort()
if not (n-1):
    print(0)
else:
    kek = List[1]-List[0]
    for i in range(n-2):
        kek = f(kek, List[i+2]-List[i+1])
    ans = ((List[n-1]-List[0])/kek + 1 - n)
    print(int(ans))



def Evkl(a, b):
    while a!=0 and b!=0:
        if a > b:
            a = a % b
        else:
            b = b % a
    return a + b

n = int(input())
string = input()
x = []
lens = []
for i in string.split(" "):
    x.append(int(i))
x.sort()
for i in range(0, n - 1):
    lens.append(abs(x[i] - x[i + 1]))
lens.sort()
min_len = lens[0]
max_len = lens[-1]
for i in range(1, n - 1):
    if min_len == 1:
        break
    if lens[i] % min_len != 0:
        min_len = Evkl(lens[i], min_len)
print(abs(x[0] - x[-1]) // min_len - n + 1)

n = int(input())
a = sorted([int(x) for x in input().split()])


def mcd(a, b):
    while a != 0 and b != 0:
        if a > b:
            a = a % b
        else:
            b = b % a
    return a + b


min_ = mcd(a[1] - a[0], a[2] - a[1])
for i in range(3, n):
    min_ = mcd(min_, a[i] - a[i - 1])
    if min_ == 1:
        break
count = 0

for i in range(1, n):
    count += (a[i] - a[i - 1]) // min_ - 1

print(count)


#python 3.5.2
import math
str=input()
n = int(str)


a = list(map(int, input().split()))
a.sort()

j=-1
for i in range(0,n-1):
    a[i]=abs(a[i]-a[i+1])
    if j==-1:
        j=a[i]
    else:
        j=math.gcd(j,a[i])
    

sum=0
for i in range(0,n-1):
    sum=sum+(a[i]//j-1)

print (sum)


def nod(a, b):
    if (b == 0):
        return a;
    else:
        return nod(b, a%b);
    
def main():
    n = int(input());
    arr = [int(i) for i in input().split()]
    arr.sort()
    no = 0;
    for i in range(1, n):
        no = nod(arr[i] - arr[i-1], no)
    ans = 0;
    for i in range(1, n):
        ans += -1 + (arr[i] - arr[i-1]) // no
    print(ans)
    
    
main()


def nod(a, b):
    while a!=0 and b!=0:
        if a > b:
            a = a % b
        else:
            b = b % a
    return (a+b)
n = int(input())
a = list(map(int, input().split()))
a.sort()
d = nod(a[1] - a[0], a[2] - a[1])
for i in range(2, n - 1):
    d = nod(a[i + 1] - a[i], d)
count = 0
for i in range(n - 1):
    count += ((a[i + 1] - a[i]) // d - 1)
print(count)
    


from fractions import gcd

n = int(input())
v = [int(x) for x in input().split()]

v.sort()

    
g = 0
last = v[0]
for i in v:
    if i != last:
        g = gcd(g, i-last)
        last = i


ans = (v[n-1] - v[0]) // g - n + 1
print(ans)














import math
from functools import reduce

n = input()

ints = [int(x) for x in input().split(' ')]
ints = sorted(ints)
dists = [ints[x]-ints[x-1] for x in range(1, len(ints))]

gcd = reduce(math.gcd, dists)

ans = reduce(lambda a,b: a + (b//gcd-1), dists, 0)

print(ans)


from fractions import gcd
n=int(input())
a=input().split()
for i in range(0, n):
    a[i]=int(a[i])

a.sort()
dists=[]
for i in range(1, n):
    dists.append(a[i]-a[i-1])
s=dists[0]
gdc=dists[0]
for i in range(1,len(dists)):
    gdc=gcd(dists[i],gdc)
    s+=dists[i]
print(s//gdc-n+1)

def gcd(x, y):
    while y != 0:
        (x, y) = (y, x % y)
    return x
a = input()
a = int(a)
x = sorted(list(map(int, input().split())))
mn = 0
cnt = 0
i = 0
for i in range(a):
     if cnt > 0:
          mn = gcd(x[i] - x[i - 1], mn)
     cnt = cnt + 1
ans = 0
cnt = 0;
i = 0
for i in range(a):
     if cnt > 0:
          ans = ans + ((x[i] - x[i - 1]) // mn - 1)
     cnt = cnt + 1
print(ans)

from fractions import gcd
n = int(input())
node = sorted(list(map(int, input().split())))


l = int(gcd(node[1] - node[0], node[2] - node[1]))

cou = int(0)
for i in range(n - 2):
    l = gcd(l, node[i + 2] - node[i + 1])


for i in range(n - 1):
    cou = int(cou + (node[i + 1] - node[i]) / l - 1)
print (cou)

import fractions
n = int(input())
s = [int(x) for x in input().split()]
s.sort(reverse=True)
nod = abs(s[0] - s[1])
for i in range(1, n):
    delta = abs(s[i] - s[i - 1])
    nod = fractions.gcd(nod, delta)
max_i = s[0]
min_i = s[-1]
print((max_i - min_i) // nod + 1 - n)

def gcd(a, b):
    while b != 0:
        tmp = a
        a = b
        b = tmp % a
    return a

input()
x = sorted([int(i) + 1000000001 for i in input().split()])

ans = x[1] - x[0]
for i in range(1, len(x)):
    ans = gcd(x[i] - x[i - 1], ans)

res = 0
for i in range(1, len(x)):
    res += (x[i] - x[i - 1]) // ans - 1

print(res)


from math import gcd

n = int(input())
a = [int(i) for i in input().split()]
a.sort()
g = 0
for i in a:
	g = gcd(g, i - a[0])
print((a[-1] - a[0]) // g - n + 1)


n = input()

x = list(map(int, input().split()))

x.sort()

def gcd(a, b):
    if (b == 0):
        return a
    else:
        return gcd(b, a % b)

g = x[1] - x[0]

for i in range(2, len(x)):
    g = gcd(g, x[i] - x[i - 1])

acc = 0;

for i in range(1, len(x)):
    acc = acc + (x[i] - x[i - 1]) / g - 1

print(int(acc))