Problem Description

Mirko lives in a small town with a port where ships rarely pass by. However, he vividly remembers the day when all the ships that visited the port appeared. He indexed this day as $1$.

Many days have passed, and Mirko has noted down the days when at least one ship visited the port, naming these days as entertainment days.

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

Given Mirko's list of entertainment days (including today, which is also an entertainment day), calculate the minimum possible number of ships that visit his port.

Note: All entertainment days are listed, and a solution is guaranteed to exist.

Input Format

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

The next $N$ lines each contain an integer $A_i$, representing the entertainment days in ascending order. The first and last entertainment days are the dates when Mirko started monitoring the port traffic and today, respectively. Today will always be listed. The first index is always $1$.

Output Format

Output a single line containing an integer, the minimum number of ships visiting Mirko's port.

Sample Input and Output

Sample Input #1

3
1
3
4

Sample Output #1

2

Sample Input #2

5
1
7
10
13
19

Sample Output #2

2

Sample Input #3

3
1
500000000
999999999

Sample Output #3

1

Notes/Hints

[Sample Explanation #1]

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

[Data Range]

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

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

[Explanation]

This problem is scored according to the original COCI settings, with a full score of $70$.

The problem is translated from COCI2010-2011 CONTEST #5 T3 BRODOVI.

见题面 Input 部分

见题面 Output 部分