У Пети есть массив состоящий из $$$n$$$ чисел и любимое число $$$k$$$.

Для любого массива Петя умеет определять его привлекательность по формуле: $$$max(array)-min(array)$$$, где $$$max(array)$$$ обозначает максимальный элемент в массиве, а $$$min(array)$$$ — минимальный элемент массива.

Для того, чтобы массив приблизился по красоте к его любимому числу, Петя может удалить не более одного элемента из этого массива. В случае если он может получить массив с привлекательностью не больше числа $$$k$$$, то он называет изначальный массив — красивым.

Петя хочет, чтобы вы ответили на $$$q$$$ его вопросов. Каждый вопрос состоит из двух чисел $$$L$$$ и $$$R$$$. Ему интересно сколько различных красивых подотрезков массива лежит внутри данного отрезка от $$$L$$$ до $$$R$$$. Более формально, вам нужно найти количество различных пар чисел «l r» для которых выполняется: $$$L \le l \lt r \le R$$$ и массив $$$a_l, a_{l + 1}, \dots, a_r$$$ является красивым.