题目描述

一名男子在 12:00 抵达了某巴士站，并且在 12：00∼12：59 期间他将在那里逗留。

巴士站有很多巴士路线，巴士抵达的时间均已给出。

该男子观察巴士的抵达时间，有所发现：

1、在 12：00∼12：59 期间，同一线路上的巴士以相同的时间间隔到站。

2、每条巴士线路至少有两辆车到达本站。

3、不同线路的巴士可以同时到达本站。

4、不同巴士线路的车首次到达本站的时间和到站的时间间隔都有可能相同。

5、测试用例中的总线路不会超过 17 条。

请你编写一个程序，求出在所有巴士到达本站的时刻满足输入数据的要求的情况下，巴士线路的总数量最小是多少。

输入格式

输入数据第一行包含整数 n，表示在这一小时内抵达到该站的巴士总数量。

第二行包含 n 个整数，表示按升序排序得到的 n 个巴士的到站时间。

输出格式

输出一个整数，表示最小巴士线路数。

样例

17
0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53

3

数据范围

$1≤n≤300$

来源

• IOI1994
• POJ1167
• 算法竞赛进阶指南