Учитывая последовательность из N чисел, извлеките количество последовательностей длины K, имеющих диапазон меньше, чем R?

Есть массив целых чисел, я должен найти количество последовательностей длиной K, имеющих диапазон (max - min подпоследовательности) меньше, чем равно R. Существует ли связь между числом последовательностей длины k и числом последовательностей длины K-1
?
Я пытаюсь решить практический вопрос по SPOJ. Я не хочу полного решения, просто укажите мне правильное направление / предложение / подсказку.

Я думал о структуре типа deque, чтобы поддерживать минимальные и максимальные элементы массива до определенного индекса. Однако, когда k ближе к n, это станет близко к o (n * n), что слишком медленно, я в идеале глядя на решение O (n) или решение O (n * log n). Было бы лучше, если бы я мог вычислить требуемое значение для K = 1 до K = N, используя отношение рекурсии / итерации, поскольку тот же ответ может потребоваться снова