Sub-Sequence Count

#1

Sub-sequence Count

You are given a sequence S consisting of N integers. Determine the number of subsequences which satisfy the following two conditions.

  1. The subsequence must be contiguous.
  2. The absolute difference between the first and the last element of the subsequence must be less than or equal to K.

Input:

First line: N (length of the sequence) and K as described the problem statement.
Next line: N space seperated integers, representing the sequence S.

Output:

For every test case, print the number of sub-sequences.

Constraints:

1 <= N <= 10^6
1 <= Si <= 10^6 (1 <= i <= N)
0 <= K <= 10^6

Sample Input:
5 3
11 5 2 15 25

Sample Output:
6

Explanation:
Valid sub-sequences are:
{11}, {5}, {2}, {15}, {25}, {5, 2}