AT_joisc2010_simroad2 シムロード (SimRoad)

在东西方向有一条笔直的道路，长度为 $L$。沿这条道路分布着 $N$ 个村庄，每个村庄的位置都用整数来表示。第 $i$ 个村庄的位置是 $x_i$（满足 $0 \le x_1 < x_2 < \cdots < x_N \le L$）。 你的任务是为这些村庄建设一定数量的车站，以确保每个村庄距离最近的车站的距离不超过 $D$。请计算为了达成这一目标，最少需要建造多少个车站。

输入包含若干组测试数据。每组数据的第一行包含三个整数：$L, N, D$（$1 \le L \le 10^9$，$1 \le N \le 100,000$，$1 \le D \le 10^9$）。接下来的一行包含 $N$ 个整数 $x_1, x_2, \ldots, x_N$，表示各个村庄的位置（满足 $0 \le x_1 < x_2 < \cdots < x_N \le L$）。 输入的最后是一个由"0 0 0"组成的行，表示输入结束。

对于每组测试数据，输出一行，表示所需建造的车站最少数量。 **本翻译由 AI 自动生成**