Minimum Number of Ships

Time limit1sMemory limit128 MB

Summary

Given the sorted list of days on which at least one periodic ship arrived, find the minimum number of periodic ships (each starting day 1) that can generate exactly that set of days.

Level: Medium7 of 10
Topics: Greedy, Math, Number theory
Solved: No attempts yet

Problem

Haebin lives in a small harbor town where ships rarely arrive. One day, every ship that had ever visited the town arrived at the same time. Haebin decided to call that day day 1.

A day is exciting if at least one ship comes to the town, and Haebin recorded every exciting day without missing any.

After watching the ships, Haebin noticed that each ship visits the harbor periodically with a fixed number of days between visits. For example, a ship with interval 3 comes on days 1, 4, 7, 10, and so on.

Today is also an exciting day. Given the complete list of exciting days up to and including today, find the minimum possible number of ships that could have produced the list. Because Haebin recorded every exciting day exactly, an answer is guaranteed to exist.

Input

The first line contains an integer N (2 ≤ N ≤ 5000), the number of exciting days.

Each of the next N lines contains one exciting day number in increasing order. The first number is always 1, and the last number is today's day number. Today's day number is less than 10^9.

Output

Print the minimum possible number of ships.

Examples3

Example 1
Input
```
3
1
3
4
```
Expected output
```
2
```
Example 2
Input
```
5
1
7
10
13
19
```
Expected output
```
2
```
Example 3
Input
```
3
1
500000000
999999999
```
Expected output
```
1
```