题目描述

一个人在 12:00 到达公交站，并停留至 12:59。该公交站有多条公交线路经过，他记录了所有公交车的到达时间（以分钟表示，范围 $0 \sim 59$）。

公交线路的规律：

• 每条线路的公交车在 12:00-12:59 期间以固定间隔到达（例如，某线路可能每 $15$ 分钟一班）。
• 每条线路至少在该小时内停靠 $2$ 次。
• 不同线路的公交车可能同时到达（即不同线路的到达时间可能相同）。
• 如果两条线路的首班车时间和间隔相同，它们仍然被视为不同的线路，并且都需要在解中体现。
• 公交线路总数不超过 $17$ 条（即需要找出最少数量的线路组合来覆盖所有记录的到达时间）。

输入

程序从标准输入读取数据：

1. 第一行：一个整数 $n$（$n \leq 300$），表示记录的公交车到达次数。
2. 第二行：$n$ 个升序排列的整数，表示公交车的到达时间（单位：分钟，范围 $0 \sim 59$）。

输出

程序向标准输出写入结果：

• 一个整数，表示最少需要多少条公交线路才能覆盖所有记录的到达时间。

输入样例 1

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

输出样例 1

3  

补充说明

• 本题属于集合覆盖问题，目标是找到最少的公交线路组合，使得所有记录的到达时间都被包含在这些线路的到站时间表中。
• 每条公交线路可以表示为一个等差数列 $T_i = \text{start} + k \times \text{interval}$，其中：
  • $\text{start}$ 是首班车时间（$0 \leq \text{start} \leq 59$）
  • $\text{interval}$ 是发车间隔（$1 \leq \text{interval} \leq 59$）
  • $k$ 为非负整数，且 $T_i \leq 59$
• 优化目标：在所有可能的线路组合中，选择线路数量最少的方案。