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
saket diwakar: 2013-01-16 11:15:45

got AC using python....
same algo in C++ is getting SIGSEGV error.... strange##

:D: 2012-12-10 21:41:52

I will help you understand this judge :)

Right now SPOJ runs all the test cases and only after that evaluates them and prints the result for the fist (I think) fail or AC if they are all correct.

Seeing input file numbers can depend on page refreshes. That's why you see 14 or 16, but it's always actually the same number.

strings: 2012-12-10 20:48:43

seriously... sometimes i am not able to understand this judge.
First, by mistake, I submitted my code of "radix sort" and it run for about 14 case- then WA.
thereafter, I used sorting in the code (which was right of course), and after 16 tc's it gave WA.
Then with reference to the comments, I just removed the sorting part, and A/C..:)

Simón Murillo Gómez: 2012-07-25 04:28:58

Easy one. by the way, no need to sort and answer will fit in int

Darky: 2012-06-19 17:29:03

fooh..finally! BTW, no need to sort!

[ !0 ]: 2011-10-28 12:44:08

Yes, coordinates are in ascending order. No need to sort them.

zayin: 2011-10-20 02:53:16

why is the answer 3 for testcase 5, 9, 11 (on the description). shouldn't it be 1 ?

Last edit: 2011-10-20 02:56:31
:D: 2011-10-08 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.

Also to all the people saying "my code works/gives correct answers". How did you check your programs? Because getting correct values for those to simple examples means exactly nothing.

sri: 2011-10-06 20:19:47

are the co ordinates given in sorted order??

sudipto das: 2011-03-22 07:50:34

are coordinates given in increasing order?
my assumption is correct.. :)

Last edit: 2011-03-22 11:14:28

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