B. Лента
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Александры есть лента, а на ней — n чисел. Обозначим их за ai слева направо.

Теперь Александра хочет разделить ленту на несколько частей (возможно, на 1). Для каждой части должны выполняться следующие условия:

  • Часть должна содержать не менее l чисел.
  • Разница между наибольшим и наименьшим числом в части должна быть не более s.

Пожалуйста, помогите Александре найти минимальное количество частей, на которые можно разделить ленту, соблюдая указанные условия.

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

В первой строке записано три разделённых пробелами целых числа n, s, l (1 ≤ n ≤ 105, 0 ≤ s ≤ 109, 1 ≤ l ≤ 105).

Во второй строке следуют n разделённых пробелами целых чисел ai ( - 109 ≤ ai ≤ 109).

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

Выведите минимальное количество частей, на которое можно разделить ленту.

Если способа разделить ленту не существует, выведите -1.

Примеры
Входные данные
7 2 2
1 3 1 2 4 1 2
Выходные данные
3
Входные данные
7 2 2
1 100 1 100 1 100 1
Выходные данные
-1
Примечание

В первом примере можно разделить ленту на 3 части: [1, 3, 1], [2, 4], [1, 2].

Во втором примере нельзя поместить 1 и 100 на одну часть, так что решения не существует.