BRODOVI - BRODOVI

Mirko lives in a small town with a harbour: once in a blue moon a ship passes by. However, to this day Mirko remembers the day when all the ships who had ever visited the harbour showed up. He denoted this day by index 1. Many days have passed since, but Mirko noted each day when at least one ship visited the harbour, naming these days entertaining. Additionally, Mirko has noticed that each ship visits the harbour periodically, at regular intervals. For instance, an interval of length 3 implies that some ship visited the harbour on days 1, 4, 7, 10 etc.

Given Mirko’s list of entertaining days (including today which is considered to be an entertaining day as well), compute the minimum possible number of ships visiting his harbour.

Notes: All entertaining days appear on Mirko’s list. It is guaranteed that the given data is consistent - in other words, a solution will always exist.

Input

The first line of input contains an integer N (2 ≤ N ≤ 5000), the number of entertaining days. The following N lines contain indices of entertaining days, one per line, in ascending order. The first and the last indices, representing the day from which Mirko started monitoring harbour traffic and today, respectively, will always appear on the list. The first index will always be 1, and the last one (index of today) will be less than 109.

Output

The first and only line of output must contain the required minimum number of ships.

Example

Input:
5
1
7
10
13
19

Output:
2

Added by:akaki
Date:2011-02-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:coci

hide comments
2018-06-25 13:45:38
Best use of Sieve :3
2015-12-17 20:39:53 MAYANK NARULA
@Pulkit Jain : Answer would be 3....

(1->7->13) of interval 6 ,
(1->25) of interval 24,
(1->37) of interval 36....

I have got it AC in one go..The problem is hence not too tough although description is poor,, comments helped a lot....remember all ships start at day 1 and they arrive 'every' time after a fixed interval is over..

( Think on the lines of Sieve of Eratosthenes )!!!...It took me an hour nearly to 'bug-free-code' the idea..!!
2015-04-17 16:44:00 Abhishek Deora
7
1
3
4
5
7
9
10
answer is 2
2014-01-30 12:45:48 ritish
@ Pulkit Jain
5

1
7
13
25
37
output = 1 (got AC !=3 && !=2)
2013-09-24 11:51:43 Pulkit Jain
@akaki -

What will be the answer of:
5

1
7
13
25
37

Should it be 2 according to the question's interpretation or 3(which got AC) and why?
2013-01-26 08:13:37 arjun
@jay Pandya ..
output:
1
1
1
find diff periods, that's enough, print only ans without \n(gives me 1 wrong ans)..
2012-06-15 13:07:20 Darky
My code seems to be correct to me. Any tricky cases?
2011-10-03 21:30:31 jack(chakradarraju)
index of the day is less than or equal to 1,000,000,000, and not 109
2011-06-04 08:04:26 .::Manish Kumar::.
little emphasis needed :: "Every ship visited at day 1. "
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.