Minimum Number of Ships

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.

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.

Print the minimum possible number of ships.