STREETR - Street Trees

no tags 

A group of trees is planted along a straight line. KOI is planning to plant more trees so that the distance between two adjacent trees is equal for all trees. For simplicity, each tree can only be planted on an integer coordinate.

For example, if 4 trees were originally planted on coordinates (1, 3, 7, 13), and if KOI plants 3 more trees on coordinates (5, 9, 11), then the distance between two adjacent trees will equal for all trees.

Your task is to calculate the minimal number of trees that KOI can plant so that the distance between two adjacent trees will equal for all trees.

Input

The first line is an integer N (3 <= N <= 100,000), which denotes the number of already planted trees.

The next N lines will have an integer X (1 <= X <= 1,000,000,000), which denotes the coordinate of each tree. 

You can safely assume that the value of X will be unique. 

Output

Output the minimal number of trees that must be planted.

Example

Input:
4
1
3
7
13

Output:
3
Input:
4
2
6
12
18

Output:
5

[Edited] Warning: Some input file contains garbage at the end.


hide comments
jawad_cs: 2017-01-03 18:37:03

Can please anybody tell me how did they solve it in O(n).
I was able to solve it in O(n*gcd(a,b)).

madhavgaba: 2016-09-14 14:26:37

really a good logic:)

poda_venna: 2016-08-30 17:45:46

Spoiler Heavy comments shall follow, beware

ace_cocytus: 2016-08-27 08:28:40

Input already sorted (If not, my solution will definitely fail).

prashu_gupta: 2016-08-03 08:19:59

my 50th! #:)

shubiks: 2016-07-10 07:27:53

You can use :
__gcd(int a,int b)
inbuilt fn to calculate gcd
Make sure you #include<algorithm>! :)

syukri: 2015-10-28 02:08:06

Accepted....in C language (0.03s)

kobe24: 2015-10-23 08:48:35

doesnt matter if input is sorted or not

shantanu tripathi: 2015-09-24 11:16:20

my 200th! :D

ihak: 2015-08-24 20:40:28

AC in python with a good complexity :)


Added by:Lawl
Date:2011-01-05
Time limit:0.203s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:2010 KOI High School Division