ST表

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 
const int N=1e6+5;
const int M=25;
const int mod=1e9+7;
int fx[N][M],fi[N][M];
int a[N],b[N];
int n,k;
int p[M];
int lg[N];
void STx() 
{
    for(int i=1; i<=n; i++) fx[i][0]=a[i];
    for(int j=1; p[j]<=n; j++) 
	{
        for(int i=1; i+p[j]-1<=n; i++) 
		{
            fx[i][j]=max(fx[i][j-1],fx[i+p[j-1]][j-1]);
        }
    }
}
int mx(int l,int r) 
{
    int len=lg[r-l+1];
    return max(fx[l][len],fx[r-p[len]+1][len]);
}

void STi() 
{
    for(int i=1; i<=n; i++) fi[i][0]=b[i];
    for(int j=1;p[j]<=n; j++) 
	{
        for(int i=1; i+p[j]-1<=n; i++) 
		{
            fi[i][j]=min(fi[i][j-1],fi[(i+p[j-1])][j-1]);
        }
    }
}

int mi(int l,int r) 
{
    int len=lg[r-l+1];
  //  cout<<len<<'\n';
//    cout<<fi[l][len]<<' '<<fi[r-p[len]+1][len]<<'\n';
    return min(fi[l][len],fi[r-p[len]+1][len]);
}

int askl(int l,int rl)
{
	int res=n;
	int L=l,R=rl;
	while(L<=R)
	{
		int mid=(L+R)>>1;
		if(mx(l,mid)>=mi(l,mid))
		{
			res=min(res,mid);
			R=mid-1;
		}
		else L=mid+1;
	}
	if(mx(l,res)!=mi(l,res))	return 0;
	return res;	
}

int askr(int l,int rr)
{
	int res=l;
	int L=l,R=rr;
	while(L<=R)
	{
		int mid=(L+R)>>1;
		if(mx(l,mid)<=mi(l,mid))
		{
			res=max(res,mid);
			L=mid+1;
		}
		else R=mid-1;
	}
	if(mx(l,res)!=mi(l,res))	return -1;
	return res;	
}

int main()
{
	scanf("%d%d",&n,&k);
	p[0]=1;
	for(int i=1;i<=25;i++)	p[i]=p[i-1]*2;
	lg[1]=0;
	for(int i=2;i<=n;i++)	lg[i]=lg[i/2]+1;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		b[i]=a[i]+k;
	}
	ll ans=0;
    STi();
    STx();
	for(int i=1;i<=n;i++)
	{
		ans+=(askr(i,n)-askl(i,n)+1);
	}
	printf("%lld\n",ans);
	return 0;
}