题目描述

一台设备产生了长度为 $n$ 的巡检序列 $a_1,a_2,\ldots,a_n$。工程师给出了一个正整数 $d$，并希望找出序列中变化规律稳定的连续区间。

对于一段连续区间 $[l,r]$，如果满足

对所有 $l\le i<r$ 都成立，那么称 $[l,r]$ 是一个稳定区间。

特别地，当 $l=r$ 时，区间中没有需要检查的相邻位置，因此每个只包含一个元素的区间都是稳定区间。

请计算序列中稳定区间的总数。

输入格式

在文件 log.in 中读入。

第一行输入两个整数 $n,d$，分别表示序列长度和规定的相邻差值。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

在文件 log.out 中输出。

输出一行一个整数，表示稳定区间的总数。

样例

样例输入 #1

8 2
10 8 6 9 7 5 3 100

样例输出 #1

17

样例 1 解释

序列可以划分为三个极大的稳定片段：

• $[10,8,6]$，其中包含 $3\times4/2=6$ 个稳定区间；
• $[9,7,5,3]$，其中包含 $4\times5/2=10$ 个稳定区间；
• $[100]$，其中包含 $1$ 个稳定区间。

因此稳定区间总数为 $6+10+1=17$。

大样例

数据范围

对于所有测试数据，保证：

答案可能超出 32 位有符号整数的表示范围。