Little Petya likes points a lot. Recently his mom has presented him n points lying on the line OX. Now Petya is wondering in how many ways he can choose three distinct points so that the distance between the two farthest of them doesn't exceed d.

Note that the order of the points inside the group of three chosen points doesn't matter.


-----Input-----

The first line contains two integers: n and d (1 ≤ n ≤ 10^5; 1 ≤ d ≤ 10^9). The next line contains n integers x_1, x_2, ..., x_{n}, their absolute value doesn't exceed 10^9 — the x-coordinates of the points that Petya has got.

It is guaranteed that the coordinates of the points in the input strictly increase.


-----Output-----

Print a single integer — the number of groups of three points, where the distance between two farthest points doesn't exceed d.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Examples-----
Input
4 3
1 2 3 4

Output
4

Input
4 2
-3 -2 -1 0

Output
2

Input
5 19
1 10 20 30 50

Output
1



-----Note-----

In the first sample any group of three points meets our conditions.

In the seconds sample only 2 groups of three points meet our conditions: {-3, -2, -1} and {-2, -1, 0}.

In the third sample only one group does: {1, 10, 20}.

Difficulty: competition

Starter code:

Solutions:
def Search(L,aa,x):
    a=aa
    b=len(L)
    while(b-a>1):
        i=(b+a)//2
        if(L[i]>x):
            b=i
        elif(L[i]<x):
            a=i
        else:
            return (i+1)-aa-1
    return b-aa-1

import math

n,d=list(map(int,input().split()))

P=list(map(int,input().split()))
ans=0
for i in range(n):
    x=Search(P,i,P[i]+d)
    if(x>1):
        ans+=((x)*(x-1))//2
print(ans)


n, d = map(int, input().split())
d += 1
t = list(map(int, input().split())) + [1000000001 + d]
s, j = 0, 2
for i in range(n - 2):
    while t[j] - t[i] < d: j += 1
    k = j - i - 1
    if k > 1: s += k *(k - 1)
print(s // 2)

n, d = map(int, input().split())
x = list(map(int, input().split()))
j, v = 0, 0
for i in range(n - 2):
    while j < n - 1 and x[j + 1] - x[i] <= d:
        j += 1
    v += (j - i) * (j - i - 1) // 2
print(v)

n, d = (int(x) for x in input().split())
x = [int(x) for x in input().split()]
l = 0
r = 0
ans = 0
while l < n:
	while r < n and x[r] - x[l] <= d:
		r += 1
	ans += (r - l - 1) * (r - l - 2) // 2
	l += 1
print(ans)


def main():
    from collections import Counter
    n, d = list(map(int, input().split()))
    l, cnt, j = list(map(int, input().split())), Counter(), 0
    for i, hi in enumerate(l):
        hi -= d
        while l[j] < hi:
            j += 1
        cnt[i - j] += 1
    print(sum(k * (k - 1) * v for k, v in list(cnt.items())) // 2)


def __starting_point():
    main()

__starting_point()

from collections import deque
n,d=map(int,input().split())
s=list(map(int,input().split()))
t=0
s1=deque()
i=0
while i<n:
    if len(s1)==0:
        s1.append(s[i])
        i+=1
    elif s[i]-s1[0]<=d:
        s1.append(s[i])
        i+=1
    else:
        m=len(s1)
        t+=(m-1)*(m-2)//2
        s1.popleft()
m=len(s1)
t+=m*(m-1)*(m-2)//6
print(t)

from collections import deque
def cxx2(x):
    #print(x)
    if(x<=1):
        return 0
    elif(x==2):
        return 1
    else:
        sans=1
        for i in range(x-1,x+1):
            sans*=i
        sans//=2
        return sans
def cxx3(x):
    #print(x)
    if(x<=2):
        return 0
    elif(x==3):
        return 1
    else:
        sans2=1
        for i in range(x-2,x+1):
            sans2*=i
        sans2//=6
        return sans2
#print(cxx3(4))
'''for i in range(10):
    print(cxx2(i))'''
inp=input().split()
n=int(inp[0])
d=int(inp[1])
inp=input().split()
a=deque()
ans=0
for i in range(n):
    a.append(int(inp[i]))
    if(len(a)!=0):
        while(a[-1]-a[0]>d):
            a.popleft()
            #print(cxx2(len(a)-1))
            ans+=cxx2(len(a)-1)
while(len(a)!=0):
    a.popleft()
    ans+=cxx2(len(a))
    #print(cxx2(len(a)))
print(ans)

n,d=[int(i) for i in input().split()]
q=list(map(int, input().split()))
s=0
if n<3:
    print(0)
else:
    t=3
    for i in range(n-2):
        for j in range(i+t-1,n):
            if q[j]-q[i]>d:
                j-=1
                break
        t=j-i
        s+=t*(t-1)//2
    print(s)


n = input().split()
a = int(n[0])
b = int(n[1])
t = input().split()
c = []
u = 0
if a <= 2:
    print(0)
    return
c.append(int(t[0]))
c.append(int(t[1]))
for i in range(2,a):
    c.append(int(t[i]))
    while c[-1] - c[0] > b:
        del c[0]
        k = len(c) - 1
        u += k * (k - 1) / 2
k = len(c)
u += k * (k - 1) * (k - 2) / 6
print(int(u))


[n,d]=[int(i) for i in input().split()];
x=[int(i) for i in input().split()];
s=0;
if(n>2):
    j=2;
    for i in range(0,n-2):
        while((j<n) and (x[j]-x[i]<=d)):
            j=j+1
        s=s+(j-i-1)*(j-i-2)//2;
    print(s);
else:
    print((0));


from collections import deque

n,m = [int(i) for i in input().split()]
list_inp = input().split()

D = deque()
ways=0
Sum=0
 
for i in range(n-1):
    while Sum+int(list_inp[i+1])-int(list_inp[i])>m and len(D)>0:
        Sum -= D.popleft()

    if Sum+int(list_inp[i+1])-int(list_inp[i]) <= m:
        ways += int(len(D)*(len(D)+1)/2)
        D.append(int(list_inp[i+1])-int(list_inp[i]))
        Sum += D[-1]
        
print (ways)
    


[n,d]=[int(i) for i in input().split()];
x=[int(i) for i in input().split()];
s=0;
if(n>2):
    j=2;
    for i in range(0,n-2):
        while((j<n) and (x[j]-x[i]<=d)):
            j=j+1
        s=s+(j-i-1)*(j-i-2)//2;
    print(s);
else:
    print((0));



from collections import deque
n,d = [int(i) for i in input().split()]
alist = [int(i) for i in input().split()]
de = deque()
i = 0
m = 0
while i < n:
    while i < n and (len(de) == 0 or alist[i] - de[0] <= d):
        de.append(alist[i])
        if len(de) >= 3:
            m += (len(de)-1) *(len(de)-2) // 2
        i += 1
    de.popleft()
print (m)

from collections import deque
n,d=[int(i) for i in input().split()]
x=[int(i) for i in input().split()]
ans=0
D=deque()
for i in range(n):
    D.append(x[i])
    if D[-1]-D[0]<=d and len(D)>=3:
        ans+=(len(D)-1)*(len(D)-2)//2
    while D[-1]-D[0]>d:
        D.popleft()
        if D[-1]-D[0]<=d:
            ans+=(len(D)-1)*(len(D)-2)//2
    #print('i',i)
    #print('D',D)
    #print('ans',ans)
print(ans)


def findIndex(x,L,R,T):
    if x[R]<T:
        return R
    if x[L]>=T:
        return L
    while R-L>1:  
        M=(R+L)//2
        if x[M]>=T:
            R=M
        else:
            L=M
    return R
        

n,d=[int(i) for i in input().split()]
x=[int(i) for i in input().split()]
ans=0
for R in range(2,n)[::-1]:
    L=findIndex(x,0,R,x[R]-d)
    ans+=(R-L)*(R-L-1)//2
print(ans)

n,d = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]

from collections import deque
D =deque()
total = 0
s = 0

for i in range(n-1):
    while len(D)>0 and s+x[i+1]-x[i] > d:
        s -= D.popleft()

    if s + x[i+1] -x[i] <= d:
        D.append(x[i+1]-x[i])
        total += (len(D)*(len(D)-1))//2
        s += D[-1]
        
print(total)


n,d = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
total = 0
position = 2

for i in range(n-2):
    l = x[i]
    distance = 1
    for j in range(position,n):
        if x[j]-l > d:
            distance = j-i-1
            position = j
            break
    else:
        distance = n-i-1
        position = n
    total += (distance*(distance-1))//2
    
print(total)

n,d=input().split(' ')
n=int(n)
d=int(d)
queue=[int(i) for i in input().split()]
ans=0
def find_max(begin,start,end):
    while start < end:
        mid=(start+end)//2
        if queue[mid]-queue[begin]<=d:
            start=mid+1
        else:
            end=mid
    mid=(start+end)//2
    if queue[mid]-queue[begin]>d:
        mid-=1
    return mid
for i in range(n-2):
    if i==0:
        j=find_max(i,i+2,n-1)
    else:
        j=find_max(i,j,n-1)
    if j-i<2:
        continue
    else:
        ans+=(j-i)*(j-i-1)//2
print(ans)

"""
Problem 2, Points on Line
Sizhang Zhao 1200011770
"""
from collections import deque

def number(D, d, length, tem):
	if tem < length:
		if tem == 0:
			start = 1
			num = 0
		else:
			start = tem 
			num = tem - 1
		for i in range(start, length):
			if D[i] - D[0] <= d:
				num += 1
			else:
				break
	else:
		num = tem - 1
	if num < 2:
		return 0
	else:
		return num 

n, d = [int(i) for i in input().split()]
numbers = [int(i) for i in input().split()]
D = deque(numbers)
leng = len(D)
times = 0
tem = 0
while leng >= 3:
	leng = len(D)
	tem = number(D, d, leng, tem)
	times += tem * (tem - 1) / 2 
	D.popleft()
print(int(times))


a,b=input().split()
n=int(a)
d=int(b)

_point=[int(i) for i in input().split()]

k=0
S=0
for i in range(2,n):
    while _point[i]-_point[k]>d:
        k+=1
    Nu=i-k
    S+=Nu*(Nu-1)//2
print(S)


from collections import deque

def comb(m):
    if m<3:
        return 0
    else:
        return int(m*(m-1)*(m-2)/6)

n,d = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
cnt = 0
de = deque()
temp = 0
for i in range(n):
    if i == 0:
        de.append(x[i])
    else:
        if de[0]+d < x[i]:
            cnt += comb(len(de))-comb(temp)
            while  len(de) != 0 and de[0]+d < x[i]:
                de.popleft()
            temp = len(de)
        de.append(x[i])
    #print(de)
cnt += comb(len(de))-comb(temp)
print(cnt)


n,d=[int(i) for i in input().split()]
jj=[int(i) for i in input().split()]
ll=0
s=0
if n<=2:
    print(0)
    return
for i in range(n-1,1,-1):
    if jj[i]-jj[s]<=d:
        ll+=(i**2-1)*i/6
        break
for j in range(i+1,n):
    while jj[j]-jj[s]>d:
        s+=1
    ll+=(j-s)*(j-s-1)/2
print(int(ll))

n,d=[int(i) for i in input().split()]
x=[int(i) for i in input().split()]

k=0
S=0

for i in range(2,n):
    while x[i]-x[k]>d:k=k+1
    P=i-k
    S+=P*(P-1)//2
    
print(S)


n,d = [int(i) for i in input().split()]
xAxis = [int(i) for i in input().split()]
cnt = 0
temp = []
temp.append(xAxis[0])

for i in range(len(temp),len(xAxis)):
    temp.append(xAxis[i])
    if temp[-1] - temp[0] > d:
        cnt += (len(temp)-2) * (len(temp)-3) /2
        del(temp[0])
        while len(temp) > 1:
            if temp[-1] - temp[0] > d:
                cnt += (len(temp)-2) * (len(temp)-3) /2
                del(temp[0])
            else: break
    if i == len(xAxis) - 1 and temp[-1] - temp[0] <= d:
        cnt += len(temp) * (len(temp)-1) * (len(temp)-2) / (3*2)

print(int(cnt))


a,b=input().split()
a=int(a)
b=int(b)
c=input().split()
for i in range(len(c)):
    c[i]=int(c[i])
x=0
t=0
for i in range(a-2):
    while (t<a and c[t]<=c[i]+b):
        t=t+1 
    t-i-1
    x=x+(t-i-1)*(t-i-2)/2
print(int(x))