P6397 [COI 2008] GLASNICI

一条直线上有 $n$ 个信使，将他们按照从左至右的顺序以 $1$ 至 $n$ 编号。换句话说，设 $i$ 号信使的的坐标为 $d_i$，则对于 $1 \leq i \lt n$， $d_i \leq d_{i + 1}$。 信使传递一条消息的方法如下： - 在任意时刻（不一定是整数时刻），任一信使（无论是否已知消息）都可以自由选择向左移动或者向右移动或者原地不动。其移动的速度为每秒 $1$ 单位长度。 - 当两个信使相距不超过一给定实数 $k$ 时，双方可以进行消息传递，也即如果两人中有一人已知该消息，则两人都知道了该消息。消息传递是瞬间发生的，不消耗时间。 现在 $1$ 号信使得到了一条消息，请求出最小的让所有信使都得到该消息的用时。

无

无

#### 样例 1 解释 在前 $1.5$ 秒，$1$ 号信使向右走，$2$ 号信使向左走。 第 $1.5$ 秒时，$1$ 号信使在坐标 $1.5$ 处，$2$ 号信使在坐标 $4.5$ 处，二者距离不超过 $3$，可以进行消息传递。 #### 数据规模与约定 对于全部的测试点，保证： - $1 \leq n \leq 10^5$，$0 \leq k \leq 10^6$。 - $0 \leq d_i \leq 10^9$，且对于任意的 $1 \leq i \lt n$，都有 $d_i \leq d_{i + 1}$。 - 输入的实数小数点后均有 $3$ 位数字。 #### 说明 **题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [COI2008](https://hsin.hr/coci/archive/2007_2008/olympiad_tasks.pdf) *T1 GLASNICI***，翻译与 SPJ 均来自[一扶苏一](https://www.luogu.com.cn/user/65363)。