CF985E.Pencils and Boxes

Mishka received a gift of multicolored pencils for his birthday! Unfortunately he lives in a monochrome world, where everything is of the same color and only saturation differs. This pack can be represented as a sequence _a_1, _a_2, ..., a__n of n integer numbers — saturation of the color of each pencil. Now Mishka wants to put all the mess in the pack in order. He has an infinite number of empty boxes to do this. He would like to fill some boxes in such a way that:

• Each pencil belongs to exactly one box;
• Each non-empty box has at least k pencils in it;
• If pencils i and j belong to the same box, then |a__i - a__j| ≤ d, where |x| means absolute value of x. Note that the opposite is optional, there can be pencils i and j such that |a__i - a__j| ≤ d and they belong to different boxes.

Help Mishka to determine if it's possible to distribute all the pencils into boxes. Print "YES" if there exists such a distribution. Otherwise print "NO".

米什卡生日时收到了一盒彩色铅笔作为礼物！但不幸的是，他生活在一个单色世界中，世间万物颜色相同，仅有饱和度不同。这盒铅笔可用一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$ 表示——其中 $a_i$ 表示第 $i$ 支铅笔的颜色饱和度。现在米什卡想把这盒杂乱的铅笔整理有序。他拥有无限多个空盒子来完成这项工作。他希望以如下方式装填若干个盒子：

• 每支铅笔恰好属于一个盒子；
• 每个非空盒子至少包含 $k$ 支铅笔；
• 若铅笔 $i$ 和铅笔 $j$ 属于同一盒子，则必须满足 $|a_i - a_j| \le d$（其中 $|x|$ 表示 $x$ 的绝对值）。注意：其逆命题不强制成立——即可能存在两支铅笔 $i$ 和 $j$，满足 $|a_i - a_j| \le d$，但它们被分到了不同的盒子中。

请帮助米什卡判断：是否能将所有铅笔按上述规则分配到盒子中？若存在这样的分配方案，则输出 "YES"；否则输出 "NO"。

The first line contains three integer numbers n, k and d (1 ≤ k ≤ n ≤ 5·105, 0 ≤ d ≤ 109) — the number of pencils, minimal size of any non-empty box and maximal difference in saturation between any pair of pencils in the same box, respectively.

The second line contains n integer numbers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109) — saturation of color of each pencil.

第一行包含三个整数 $n$、$k$ 和 $d$（$1 \le k \le n \le 5\cdot10^5$，$0 \le d \le 10^9$），分别表示铅笔的数量、任意非空盒子的最小容量，以及同一盒子中任意两支铅笔饱和度之差的最大允许值。

第二行包含 $n$ 个整数 $a_1,\,a_2,\,\dots,\,a_n$（$1 \le a_i \le 10^9$），表示每支铅笔的颜色饱和度。

Print "YES" if it's possible to distribute all the pencils into boxes and satisfy all the conditions. Otherwise print "NO".

如果可以将所有铅笔分配到盒子中并满足所有条件，则输出“YES”；否则输出“NO”。

In the first example it is possible to distribute pencils into 2 boxes with 3 pencils in each with any distribution. And you also can put all the pencils into the same box, difference of any pair in it won't exceed 10.

In the second example you can split pencils of saturations [4, 5, 3, 4] into 2 boxes of size 2 and put the remaining ones into another box.

在第一个例子中，可以将铅笔分配到 2 个盒子中，每个盒子恰好装 3 支铅笔，且这种分配方式对任意分布均成立。此外，你也可以将所有铅笔放入同一个盒子中，此时该盒子中任意一对铅笔的饱和度之差均不超过 10。

在第二个例子中，你可以将饱和度为 [4, 5, 3, 4] 的铅笔分成 2 个大小均为 2 的盒子，并将剩余的铅笔放入另一个盒子中。