Description

给定一个n个整数的序列以及一个非负整数d，请你输出这个序列中有多少个连续子序列（长度大于1），满足该子序列的最大值最小值之差不大于d。

如，序列1 2 5中长度大于1的连续子序列有：

1 2

2 5

1 2 5

该子序列最大值最小值之差不大与2的子序列有1个：

1 2

Input Format

第一行包含两个整数n,d。（1<=n<=300000, 0<=d<=2000000000）

接下来一行包含n个整数。

Output Format

输出一个整数，表示满足条件的连续子序列个数。

8 5
5 5 4 8 -10 10 0 1​

7​

Hint

数据量大，请程序避免超时

样例1的解释：

满足条件的连续子序列有：

5 5

5 5 4

5 5 4 8

5 4

5 4 8

4 8

0 1

Source

分治