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, \ldots\)

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.

In test cases worth 70% of total points, day indices will be less than 5 000 000.

The first line of input contains an integer \(N\) (\(2 \le N \le 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 \(10^9\).

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

riseoj 작성

출처 COCI 2010/2011 Contest 5