E. Коробки с карандашами
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На день рождения Мишка получил в подарок разноцветные карандаши! К сожалению, он живет в монохромном мире, где все одного и того же цвета, и имеет смысл исключительно насыщенность цвета. Эту упаковку можно представить в виде последовательности a1, a2, ..., an из n целых чисел — насышенность цвета каждого карандаша. Теперь Мишка хочет навести порядок в этой упаковке. Для этого он подготовил бесконечное количество пустых коробок. Он хочет их заполнить таким образом, чтобы:

  • Каждый карандаш лежал ровно в одной коробке;
  • В каждой непустой коробке лежало не меньше k карандашей;
  • Если карандаши i и j лежат в одной и той же коробке, то |ai - aj| ≤ d, где |x| означает модуль числа x. Обратите внимание, что обратное условие может не выполняться, могут быть такие карандаши i и j, что |ai - aj| ≤ d и они лежат в различных коробках.

Помогите Мишке определить, можно ли распределить все карандаши по коробкам. Выведите "YES", если существует такое распределение. Иначе выведите "NO".

Входные данные

В первой строке записаны три целых числа n, k и d (1 ≤ k ≤ n ≤ 5·105, 0 ≤ d ≤ 109) — количество карандашей, минимальный размер любой непустой коробки и максимальная разница в насыщенности какой-либо пары карандашей, лежащих в одной коробке, соответственно.

Во второй строке записаны n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109) — насыщенности цветов каждого карандаша.

Выходные данные

Выведите "YES", если можно распределить все карандаши по коробкам так, чтобы все условия выполнялись. Иначе выведите "NO".

Примеры
Входные данные
6 3 10
7 2 7 7 4 2
Выходные данные
YES
Входные данные
6 2 3
4 5 3 13 4 10
Выходные данные
YES
Входные данные
3 2 5
10 16 22
Выходные данные
NO
Примечание

В первом примере можно разделить все карандаши на 2 коробки по 3 карандаша любым образом. Также можно положить все карандаши в одну коробку, разница в насыщенности между любой парой карандашей в ней не будет превосходить 10.

Во втором примере можно разделить карандаши насыщенностей [4, 5, 3, 4] на 2 коробки размера 2 и положить оставшиеся в еще одну коробку.