题目描述

Mirko 住在一个难得有船经过的有港口的小镇上。然而，直到今天，Mirko 还记得那天所有造访过这个港口的船只都出现了。他用索引 $1$ 表示这一天。

许多天过去了，Mirko 记下了至少有一艘船访问港口的日子，把这些日子命名为娱乐日。

此外，Mirko 注意到每艘船都定期访问港口。例如，长度为 $3$ 的间隔表示某艘船在第 $1$ 天、第 $4$ 天、第 $7$ 天、第 $10$ 天等时间访问港口。

给出 Mirko 的娱乐日列表（包括今天，且今天也是一个娱乐日），计算访问他的港口的最小可能的船只数量。

注:所有娱乐日都出现在 Mirko 的列表上，保证永远存在答案。

输入格式

输入的第 $1$ 行包含一个整数 $N$，即娱乐天的个数。

下面 $N$ 行，每行一个整数 $A_i$，表示表上的娱乐天数，按升序排列。第一个和最后一个娱乐天分别是 Mirko 开始监测港口交通的日期和今天。今天将一直出现在列表上。第一个索引总是 $1$。

输出格式

输出共一行，一个整数，为最小的访问 Mirko 的港口的船舶的数量。

3
1
3
4 

2

5
1
7
10
13
19 

2

3
1
500000000
999999999

1

提示

【样例说明#1】

最少需要两条船，第一条每 $2$ 天来一次，第二条每 $3$ 天来一次。

【数据范围】

对于 $70\%$ 的数据，$A_i\le 5\times 10^6$

对于 $100\%$ 的数据，$2\le N\le 5000$，$1 \le A_i\le 10^9$

【说明】

【说明】

本题分值按 COCI 原题设置，满分 $70$。

题目译自 COCI2010-2011 CONTEST #5 T3 BRODOVI。