STREETR  Street Trees
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
mynk322:
20180906 10:27:34
AC in one go!!!!!!!!


aditya9125:
20171007 21:31:05
simple !


sophozaar:
20171001 17:31:00
This problem improved my implementation skills


nilabja16180:
20170327 17:30:26
AC IN ONE GO! 

shubham_cs_iet:
20170112 16:42:30
AC in C in 0.02 sec. ;) 

jawad_cs:
20170103 18:37:03
Can please anybody tell me how did they solve it in O(n).


madhavgaba:
20160914 14:26:37
really a good logic:) 

poda_venna:
20160830 17:45:46
Spoiler Heavy comments shall follow, beware 

ace_cocytus:
20160827 08:28:40
Input already sorted (If not, my solution will definitely fail). 

prashu_gupta:
20160803 08:19:59
my 50th! #:) 
Added by:  Lawl 
Date:  20110105 
Time limit:  0.203s0.611s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  2010 KOI High School Division 