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
sudipto das:
20110322 07:50:34
are coordinates given in increasing order?


Vivek Bhavsar:
20110212 21:32:08
how to get test cases ? 

Shubham Maheshwari:
20110123 18:39:22
is there an extra new line character in the input test cases ...??? 

:D:
20110122 01:31:22
I DIDN'T assume that. The description says nothing about it, so probably not. 

SIGSEGV:
20110122 01:31:22
Are the coordinates in ascending order? 

LeppyR64:
20110122 01:31:22
The constraint for n is fine. X <= 10^9, not 10^8.


Luke Pebody:
20110122 01:31:22
The tests seem to have some error data in them. scanf'ing an n, and then n x's, and asserting the bounds specified in the question causes SIGABRT. 

Michael T:
20110122 01:31:22
Still garbage in the end I guess. 

:D:
20110122 01:31:22
Like in case of other problems, NO. You have figure out on your own what kind of situations may occur in tests. 

Manish :
20110122 01:31:22
is it possible for us to see Test case? 
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 