Вам дан массив \(a\) из \(n\) целых чисел, а также целое число \(k\).
Пара индексов \((l,r)\) называется хорошей, если существует последовательность индексов \(i_1, i_2, \dots, i_m\) такая, что
- \(i_1=l\) и \(i_m=r\);
- \(i_j < i_{j+1}\) для всех \(1 \leq j < m\); а также
- \(|a_{i_j}-a_{i_{j+1}}| \leq k\) для всех \(1 \leq j < m\).
Найдите количество хороших пар \((l,r)\) (\(1 \leq l \leq r \leq n\)).
Примечание
В первом примере хорошие пары равны \((1,1)\), \((1,2)\), \((1,3)\), \((2,2)\), \((2,3)\) и \((3,3)\).
Во втором примере хорошие пары равны \((1,1)\), \((1,3)\), \((1,4)\), \((2,2)\), \((2,3)\), \((2,4)\), \((3,3)\), \((3,4)\) и \((4,4)\). Пара \((1,4)\) является хорошей, так как существует последовательность индексов \(1, 3, 4\), удовлетворяющая всем ограничениям.