У Александры есть лента, а на ней — n чисел. Обозначим их за ai слева направо.
Теперь Александра хочет разделить ленту на несколько частей (возможно, на 1). Для каждой части должны выполняться следующие условия:
- Часть должна содержать не менее l чисел.
- Разница между наибольшим и наименьшим числом в части должна быть не более s.
Пожалуйста, помогите Александре найти минимальное количество частей, на которые можно разделить ленту, соблюдая указанные условия.
Выходные данные
Выведите минимальное количество частей, на которое можно разделить ленту.
Если способа разделить ленту не существует, выведите -1.
Примечание
В первом примере можно разделить ленту на 3 части: [1, 3, 1], [2, 4], [1, 2].
Во втором примере нельзя поместить 1 и 100 на одну часть, так что решения не существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 2 2
1 3 1 2 4 1 2
|
3
|
|
2
|
7 2 2
1 100 1 100 1 100 1
|
-1
|