该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个长度为 $m$ 的序列 $b$，我们称 $b$ 是“好序列”，当且仅当序列的极差不超过一个常数 $k$，即：

其中，$\max_{i=1}^{m} b_i$ 表示序列 $b$ 中 $m$ 个元素的最大值，$\min_{i=1}^{m} b_i$ 表示序列 $b$ 中 $m$ 个元素的最小值。

现在给定一个长度为 $n$ 的序列 $a$，你需要求出 $a$ 有多少个非空子数组是“好序列”。

注：一个序列 $x$ 是另一个序列 $y$ 的子数组，当且仅当 $x$ 可以通过 $y$ 删除开头任意个和结尾任意个元素（可以为 $0$ 个）得到，即子数组必须是原序列中连续的一段。

输入格式

第一行包含两个整数 $n, k$，分别表示序列的长度和题目描述中的常数 $k$。

第二行包含 $n$ 个整数，第 $i$ 个数表示 $a_i$。

输出格式

输出一行一个整数，表示“好序列”子数组的数量。

6 3
1 1 4 5 1 4

11

满足条件的子数组（下标区间 $[l, r]$）如下：

长度为 $1$： $[1,1], [2,2], [3,3], [4,4], [5,5], [6,6]$（极差均为 $0$），共 $6$ 个。

长度为 $2$： $[1,2]$ (极差 $0$), $[2,3]$ (极差 $3$), $[3,4]$ (极差 $1$), $[5,6]$ (极差 $3$)，共 $4$ 个。 注意 $[4,5]$ 极差为 $4>3$ 不满足。

长度为 $3$： $[1,3]$ (极差 $3$)，共 $1$ 个。

总计 $6+4+1=11$ 个。

数据规模与约定

对于 $100$ 的数据，$1 \le n \le 5000$，$0 \le k, a_i \le 10^9$。