Mirko 居住在一个带港口的小镇上：极少有船只经过。然而，直到今天，Mirko 依然记得所有曾经访问过该港口的船只同时出现的那一天。他将这一天记为第 1 天。

自那以后已经过去了许多天，但 Mirko 记录下了每天至少有一艘船访问港口的日子，并将这些日子称为“有趣的”日子。

此外，Mirko 注意到每艘船都是周期性地、以固定的时间间隔访问港口。例如，长度为 3 的间隔意味着某艘船会在第 1, 4, 7, 10 等天访问港口。

给定 Mirko 的有趣日子列表（包括今天，今天也被认为是一个有趣的日子），计算访问他港口的最少可能船只数量。

注意：所有有趣的日子都出现在 Mirko 的列表中。保证给定的数据是一致的——换句话说，一定存在解。

输入格式

输入的第一行包含一个整数 $N$ ($2 \le N \le 5000$)，表示有趣日子的数量。

接下来的 $N$ 行按升序包含有趣日子的天数编号，每行一个。第一个和最后一个编号分别代表 Mirko 开始监控港口交通的那一天和今天，它们总是会出现在列表中。第一个编号总是 1，最后一个编号（今天的编号）将小于 $10^9$。

输出格式

输出的第一行也是唯一的一行，包含所需的最小船只数量。

子任务

在占总分 70% 的测试用例中，天数编号将小于 $5\,000\,000$。

样例

输入样例 1

3
1
3
4

输出样例 1

2

输入样例 2

5
1
7
10
13
19

输出样例 2

2

输入样例 3

3
1
500000000
999999999

输出样例 3

1