Description

Mirko lives in a small town with a harbor where ships rarely pass by. However, even today, Mirko still remembers the day when all ships that had ever visited this harbor showed up. He labels that day with index $1$.

Many days have passed, and Mirko recorded the days on which at least one ship visited the harbor, calling these days "fun days".

Also, Mirko noticed that each ship visits the harbor periodically. For example, an interval of length $3$ means that a ship visits on day $1$, day $4$, day $7$, day $10$, and so on.

Given Mirko's list of fun days (including today, and today is also a fun day), compute the minimum possible number of ships that visited his harbor.

Note: All fun days are included in Mirko's list, and it is guaranteed that an answer always exists.

Input Format

The first line contains an integer $N$, the number of fun days.

The next $N$ lines each contain an integer $A_i$, representing the fun days on the list, in increasing order. The first and last fun days are the day Mirko started monitoring the harbor traffic and today, respectively. Today will always appear in the list. The first index is always $1$.

Output Format

Output one line with one integer: the minimum number of ships that visited Mirko's harbor.

3
1
3
4 

2

5
1
7
10
13
19 

2

3
1
500000000
999999999

1

Hint

[Sample Explanation #1]

At least two ships are needed: the first comes every $2$ days, and the second comes every $3$ days.

[Constraints]

For $70\%$ of the testdata, $A_i \le 5 \times 10^6$.

For $100\%$ of the testdata, $2 \le N \le 5000$, $1 \le A_i \le 10^9$.

[Notes]

[Notes]

The score of this problem follows the original COCI settings, with a full score of $70$.

Translated from COCI2010-2011 CONTEST #5 T3 BRODOVI.

Translated by ChatGPT 5