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
hide comments
mag1x_:
20180625 13:45:38
Best use of Sieve :3 

MAYANK NARULA:
20151217 20:39:53
@Pulkit Jain : Answer would be 3....


Abhishek Deora:
20150417 16:44:00
7


ritish:
20140130 12:45:48
@ Pulkit Jain


Pulkit Jain:
20130924 11:51:43
@akaki 


arjun:
20130126 08:13:37
@jay Pandya ..


Darky:
20120615 13:07:20
My code seems to be correct to me. Any tricky cases? 

Rajkiran Rajkumar:
20120405 18:21:45
Last edit: 20120405 18:22:46 

jack(chakradarraju):
20111003 21:30:31
index of the day is less than or equal to 1,000,000,000, and not 109 
Added by:  akaki 
Date:  20110215 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  coci 