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
saket diwakar:
20130116 14:00:29
finally found the error....


saket diwakar:
20130116 11:15:45
got AC using python....


:D:
20121210 21:41:52
I will help you understand this judge :)


strings:
20121210 20:48:43
seriously... sometimes i am not able to understand this judge.


Simón Murillo Gómez:
20120725 04:28:58
Easy one. by the way, no need to sort and answer will fit in int 

Darky:
20120619 17:29:03
fooh..finally! BTW, no need to sort! 

[ !0 ]:
20111028 12:44:08
Yes, coordinates are in ascending order. No need to sort them. 

zayin:
20111020 02:53:16
why is the answer 3 for testcase 5, 9, 11 (on the description). shouldn't it be 1 ? Last edit: 20111020 02:56:31 

:D:
20111008 07:44:31
If the description doesn't say anything about the order, don't assume it's sorted I already wrote that below, read other comments before posting questions.


sri:
20111006 20:19:47
are the co ordinates given in sorted order??

Added by:  Lawl 
Date:  20110105 
Time limit:  0.203s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  2010 KOI High School Division 