You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

给定一个长度为 $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$。

输出格式

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

样例

样例输入 #1

6 3
1 1 4 5 1 4

样例输出 #1

11

样例解释 #1

满足条件的子数组（下标区间 $[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$。