问题描述

白巫师萨鲁曼必须率领军队沿一条笔直的路径从艾森加德前往海尔姆深谷。为了掌握部队动向，萨鲁曼在军队中部署真知晶球（palantirs）。每个真知晶球的最大有效范围为$R$单位，且必须由军队中的某个士兵携带（即真知晶球不能“悬浮”在半空中）。请帮助萨鲁曼确定所需真知晶球的最小数量，确保每个士兵都位于至少一个真知晶球的有效范围内（即与某个携带晶球的士兵的距离不超过$R$）。

输入

输入包含多组测试用例。每组用例的第一行包含两个整数$R$（真知晶球的最大有效范围，$0 \leq R \leq 1000$）和$n$（军队中的士兵数量，$1 \leq n \leq 1000$）。下一行包含$n$个整数，表示每个士兵的位置$x_1, x_2, \dots, x_n$（$0 \leq x_i \leq 1000$）。输入以$R = n = -1$结束。

输出

对每组测试用例，输出所需真知晶球的最小数量。

输入输出示例

输入数据 1

0 3  
10 20 20  
10 7  
70 30 1 7 15 20 50  
-1 -1  

输出数据 1

2  
4  

提示

• 第一组用例中，萨鲁曼可在位置10和20各放置一个真知晶球。注意，范围为0的晶球可覆盖位置20的两个士兵（因晶球必须由士兵携带，故两个士兵在同一位置时，一个晶球即可覆盖）。
• 第二组用例中，晶球可放置在位置7（覆盖1、7、15）、20（覆盖20、30）、50、70。注意，晶球必须由士兵携带，因此不能在位置60放置晶球来覆盖50和70的士兵（因60处无士兵）。

来源

Stanford Local 2006