#include <bits/stdc++.h>
#include <string>
#include <deque>
#include <algorithm>
using namespace std;
#define abs(x) (x < 0 ? -x : x)
#define CHUNCK 256
#define CSHIFT 8
struct Val{
int val;
int loc;
friend bool operator < (Val const &a, Val const &b){
return a.val < b.val;
}
};
struct Extreme{
Val min;
Val max;
Extreme(){}
Extreme(int val, int pos) : min({val, pos}), max({val, pos}){}
inline int diff(){ return max.val - min.val; }
};
int main(int argv, char *argc[]){
int len, diff;
cin >> len >> diff;
int *numbers = new int[len];
// Chunck minimum/maximum values
Extreme *chunkExtremes = new Extreme[(len >> CSHIFT) + 1]();
for_each(numbers, numbers + len, [](auto &el){
cin >> el;
});
long result = 0;
static_assert(sizeof(long) == 8);
int index = 0; // Current index
int s = 0; // Start position of the sublist
int cV; // Current value
int extremeListIncrement;
int exlI;
int exlImin;
Extreme sle; // The extremes of current sublist
emptySList:
s = index;
sle = Extreme(numbers[index], index);
extremeListIncrement = 0;
exlImin = exlI = 0;
chunkExtremes[exlI] = sle;
while(++index < len){
cV = numbers[index];
if(cV <= sle.min.val){
if(sle.min.val - cV > diff){
// None of the current sub list fit...
long n = index - s;
result += (n*n + n) >> 1;
goto emptySList;
}
sle.min = {cV, index};
if(sle.diff() > diff){
// Find the most rescent chunck in which the maximum does not fit.
int i;
int searchS = -1;
Val mx = {0};
for(i = exlI; i >= exlImin; i--){
if(chunkExtremes[i].max.val - cV > diff){
searchS = chunkExtremes[i].max.loc + 1;
break;
}else mx = max(mx, chunkExtremes[i].max);
}
exlImin = i;
int chunckLast = index - extremeListIncrement - 2 - (exlI - i - 1) * CHUNCK;
int searchE = min(index - 1, chunckLast);
chunkExtremes[i] = Extreme(numbers[searchE + 1], searchE + 1);
assert(searchS != -1);
// Look for values between searchS and searchE, and look for first
// one that does not fit...
for(; searchE >= searchS && numbers[searchE] - cV <= diff; searchE--){
if(numbers[searchE] < chunkExtremes[i].min.val){
chunkExtremes[i].min = {numbers[searchE], searchE};
}else if(numbers[searchE] > chunkExtremes[i].max.val){
chunkExtremes[i].max = {numbers[searchE], searchE};
}
}
if(searchE >= chunckLast) exlImin++;
sle.max = max(chunkExtremes[exlImin].max, mx);
// searchE now points to the last discarded value, therefore, values
// between s and searchE discarded.
// All numbers from s to n are to be discarded
int n = searchE - s + 1;
result += (long)(2*index - 2*s - n + 1) * n >> 1;
s+= n;
}
} else if(cV >= sle.max.val){
if(cV - sle.max.val> diff){
// None of the current sub list fit...
long n = index - s;
result += (n*n + n) >> 1;
goto emptySList;
}
sle.max = {cV, index};
if(sle.diff() > diff){
// Find the most rescent chunck in which the minimum does not fit.
int i;
int searchS;
Val mn = {2000000000};
for(i = exlI; i >= exlImin; i--){
if(cV - chunkExtremes[i].min.val > diff){
searchS = chunkExtremes[i].min.loc + 1;
break;
}else mn = min(mn, chunkExtremes[i].min);
}
exlImin = i;
int chunckLast = index - extremeListIncrement - 2 - (exlI - i - 1) * CHUNCK;
int searchE = min(index - 1, chunckLast);
chunkExtremes[i] = Extreme(numbers[searchE + 1], searchE + 1);
// Look for values between searchS and searchE, and look for first
// one that does not fit...
for(; searchE >= searchS && cV - numbers[searchE] <= diff; searchE--){
if(numbers[searchE] < chunkExtremes[i].min.val){
chunkExtremes[i].min = {numbers[searchE], searchE};
}else if(numbers[searchE] > chunkExtremes[i].max.val){
chunkExtremes[i].max = {numbers[searchE], searchE};
}
}
if(searchE >= chunckLast) exlImin++;
sle.min = min(chunkExtremes[exlImin].min, mn);
// searchE now points to the last discarded value, therefore, values
// between s and searchE discarded.
// All numbers from s to n are to be discarded
int n = searchE - s + 1;
result += (long)(2*index - 2*s - n + 1) * n >> 1;
s+= n;
}
}
// Chunck management
if(++extremeListIncrement >= CHUNCK){
extremeListIncrement = 0;
exlI++;
chunkExtremes[exlI] = Extreme(index, cV);
}else if(cV <= chunkExtremes[exlI].min.val){
chunkExtremes[exlI].min = {cV, index};
}else if(cV >= chunkExtremes[exlI].max.val){
chunkExtremes[exlI].max = {cV, index};
}
}
long n = index - s;
result += (n*n + n) >> 1;
cout << result << endl;
return EXIT_SUCCESS;
}
