Minimum Number of Ships

Mirko lives in a port town where ships rarely pass by. He still remembers the day when every ship that visited the port came – he calls that day day 1. Many days have passed since then. Mirko recorded all days on which at least one ship visited and called these days fun days.

Moreover, Mirko noticed that each ship visits the port periodically. For example, a ship with an interval of $3$ will visit on days $1$, $1+3=4$, $4+3=7$, $7+3=10$, and so on.

Given the list of fun days (which includes day 1 as well as today – today is also a fun day), determine the minimum possible number of ships whose periodic schedules could have produced exactly the recorded fun days. Note that if a ship has a periodic interval $d$ and its first visit is on day $a$, then for every nonnegative integer $k$ with $a+k\,d \le L$ (where $L$ is the last recorded day), the day $a+k\,d$ must be a fun day. In other words, no ship is allowed to "skip" a scheduled visit.

You may assume that a valid solution always exists.

inputFormat

The input consists of two lines. The first line contains a single integer $N$ ($1 \le N \le 20$), the number of fun days recorded. The second line contains $N$ space‐separated positive integers in strictly increasing order, representing the fun days. It is guaranteed that the first day is $1$ and the last day represents today.

outputFormat

Output a single integer: the minimum number of ships that could have visited the port such that their periodic schedules exactly cover the given fun days.

sample

3
1 3 7

2