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}.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Combinatorics

Amortized analysis


Solutions:
(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))


from bisect import *
(n, d) = map(int, input().split())
ar = list(map(int, input().split()))
s = 0
for i in range(n):
	j = bisect_left(ar, ar[i] - d)
	N = i - j
	s += N * (N - 1) // 2
print(s)


def lower_bound(lst, low, upp, target):
	while upp - low > 1:
		mid = (upp + low) // 2
		if lst[mid] > target:
			upp = mid
		elif lst[mid] < target:
			low = mid
		else:
			return mid
	return low

def main():
	(n, d) = [int(i) for i in input().split()]
	xx = [int(i) for i in input().split()]
	if n < 3:
		print(0)
		return
	total_num = 0
	for i in range(n - 2):
		lth = lower_bound(xx, i, n, xx[i] + d) - i
		num = lth * (lth - 1) / 2
		total_num += num
	print(int(total_num))
main()


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


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
ret = 0
for (i, val) in enumerate(a):
	(left, right) = (i - 1, n)
	while left + 1 < right:
		mid = left + right >> 1
		if a[mid] - val > d:
			right = mid
		else:
			left = mid
	if left != i - 1:
		size = left - i - 1
		ret += size * (size + 1) // 2
print(ret)


(n, d) = map(int, input().split())
arr = list(map(int, input().split()))
ans = 0
l = 0
r = 0
b = {}
while l <= r and r < len(arr):
	if r - l < 2:
		r += 1
		continue
	if arr[r] - arr[l] > d:
		l += 1
		continue
	if r not in b:
		b[r] = l
	else:
		b[r] = min(b[r], l)
	if r != len(arr) - 1:
		r += 1
	else:
		l += 1
for (v, k) in b.items():
	if v - k < 2:
		continue
	ans += (v - k) * (v - k - 1) // 2
print(ans)


def R():
	return map(int, input().split())

def I():
	return int(input())

def S():
	return str(input())

def L():
	return list(R())
from collections import Counter
import math
import sys
from itertools import permutations
import bisect
mod = 10 ** 9 + 7
(n, d) = R()
x = L() + [10000000000.0]
x.sort()
l = 0
r = 0
ans = 0
while r < n:
	while r + 1 <= n and x[r + 1] - x[l] <= d:
		r += 1
	ans += (r - l - 1) * (r - l) // 2
	l += 1
print(ans)


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(ans)


import operator as op
from functools import reduce
import bisect

def ncr(n, r):
	if n < r:
		return 0
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom

def main():
	(n, d) = map(int, input().split())
	coords = list(map(int, input().split()))
	ans = 0
	prev_j = 0
	for i in range(n):
		curr = coords[i] + d
		j = bisect.bisect(coords, curr) - 1
		if i == 0:
			ans += ncr(j - i + 1, 3)
		else:
			ans += ncr(prev_j - i + 1, 2) * (j - prev_j)
			ans += ncr(j - prev_j, 2) * (prev_j - i + 1)
			ans += ncr(j - prev_j, 3)
		prev_j = j
	print(ans)
main()


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


from sys import *
from math import *
(n, k) = map(int, stdin.readline().split())
a = list(map(int, stdin.readline().split()))
ans = 0
for i in range(n - 2):
	x = a[i] + k
	l = i + 2
	h = n - 1
	j = 0
	f = 0
	while l <= h:
		m = (l + h) // 2
		if a[m] > x:
			h = m - 1
		elif a[m] <= x:
			j = m
			l = m + 1
			f = 1
	if f == 1:
		y = j - i - 2
		ans += (y + 1) * (y + 2) // 2
print(ans)


def PL(arr, n, k):
	j = 0
	aux = 0
	for i in range(len(arr)):
		while arr[i] - arr[j] > k:
			j += 1
		aux += (i - j) * (i - j - 1) // 2
	return aux
arr = []
(n, k) = list(map(int, input().strip().split()))
arr = list(map(int, input().strip().split()))
print(PL(arr, n, k))


def points_on_line(l, d):
	j = 0
	combination = 0
	for i in range(len(l)):
		while j < len(l) and l[j] <= l[i] + d:
			j += 1
		nums = j - i - 1
		combination += nums * (nums - 1) // 2
	return combination
(n, d) = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
print(points_on_line(l, d))


import time, math as mt, bisect as bs, sys
from sys import stdin, stdout
from collections import defaultdict
from collections import deque
from fractions import Fraction
from collections import Counter
from collections import OrderedDict
pi = 3.141592653589793

def II():
	return int(stdin.readline())

def IO():
	return stdin.readline()

def IP():
	return map(int, stdin.readline().split())

def L():
	return list(map(int, stdin.readline().split()))

def P(x):
	return stdout.write(str(x) + '\n')

def PI(x, y):
	return stdout.write(str(x) + ' ' + str(y) + '\n')

def lcm(a, b):
	return a * b // gcd(a, b)

def gcd(a, b):
	if a == 0:
		return b
	elif b == 0:
		return a
	if a > b:
		return gcd(a % b, b)
	else:
		return gcd(a, b % a)

def readTree():
	v = int(input())
	adj = [set() for i in range(v + 1)]
	for i in range(v - 1):
		(u1, u2) = In()
		adj[u1].add(u2)
		adj[u2].add(u1)
	return (adj, v)

def bfs(adj, v):
	visited = [False] * (v + 1)
	q = deque()
	while q:
		pass

def sieve():
	li = [True] * 1000001
	(li[0], li[1]) = (False, False)
	for i in range(2, len(li), 1):
		if li[i] == True:
			for j in range(i * i, len(li), i):
				li[j] = False
	prime = []
	for i in range(1000001):
		if li[i] == True:
			prime.append(i)
	return prime

def setBit(n):
	count = 0
	while n != 0:
		n = n & n - 1
		count += 1
	return count
mx = 10 ** 7
spf = [mx] * (mx + 1)

def SPF():
	spf[1] = 1
	for i in range(2, mx + 1):
		if spf[i] == mx:
			spf[i] = i
			for j in range(i * i, mx + 1, i):
				if i < spf[j]:
					spf[j] = i
	return
mod = 10 ** 9 + 7

def solve():
	(n, d) = IP()
	li = L()
	mov = 0
	for i in range(n - 2):
		x = i + 2
		if li[x] - li[i] <= d:
			y = bs.bisect_left(li, li[i] + d)
			if y >= n:
				ind = y - x
			else:
				if li[y] - li[i] > d:
					y -= 1
				ind = y - x + 1
			mov += ind * (ind + 1) // 2
	P(mov)
	return
t = 1
for i in range(t):
	solve()


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


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


(n, d) = map(int, input().split())
ar = list(map(int, input().split()))
(i, j, s) = (0, 0, 0)
while i < n:
	while ar[i] - ar[j] > d:
		j += 1
	N = i - j
	s += N * (N - 1) // 2
	i += 1
print(s)


import os
import sys
from io import BytesIO, IOBase
from bisect import bisect

def ncr(n, r):
	return n * (n - 1) // 2

def main():
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		z = bisect(l, l[i] + d)
		ans += ncr(z - i - 1, 2)
	print(ans)

def nouse0():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse1():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse2():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


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


[n, d] = list(map(int, input().split()))
nums = list(map(int, input().split()))
i = l = 0
p = r = 2
while l < n - 2 and r < n:
	x = nums[l]
	r = max(p, l + 2)
	while r < n:
		if nums[r] - x > d:
			p = r
			break
		i += (r - l - 1) * (r - l) / 2
		r += 1
	l += 1
print(int(i))


import bisect
I = lambda : map(int, input().rstrip().split())
(n, d) = I()
x = list(I())
ans = 0

def getCount(m):
	return m * (m - 1) // 2
for i in range(n - 2):
	a = x[i]
	c = a + d
	ind = bisect.bisect_left(x, c)
	if ind > n - 1:
		ind = n - 1
	elif x[ind] != c:
		ind -= 1
	ans += getCount(ind - i)
print(ans)


(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)


from collections import deque

def cxx2(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):
	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
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()
			ans += cxx2(len(a) - 1)
while len(a) != 0:
	a.popleft()
	ans += cxx2(len(a))
print(ans)


from bisect import bisect_right
(num_points, max_distance) = map(int, input().split())
points = list(map(int, input().split()))
solution = 0
for (pos_point_min, point_min) in enumerate(points):
	point_max = point_min + max_distance
	pos_point_max = bisect_right(points, point_max) - 1
	num_middle_points = pos_point_max - pos_point_min
	if num_middle_points > 0:
		solution += num_middle_points * (num_middle_points - 1) // 2
print(solution)


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


I = lambda : list(map(int, input().split()))
(n, d) = I()
x = I()
(l, r, ans) = (0, 0, 0)
while r < n and x[r] - x[l] <= d:
	r += 1
ans += (r - l) * (r - l - 1) * (r - l - 2) // 6
while r < n:
	while l < r and x[r] - x[l] > d:
		l += 1
	ans += (r - l) * (r - l - 1) // 2
	r += 1
print(ans)


from sys import stdin
(a, b) = map(int, stdin.readline().split())
z = list(map(int, stdin.readline().split()))
(i, j) = (0, 0)
ans = 0
r = lambda x: x * (x + 1) // 2
while i < a:
	while j < a and abs(z[j] - z[i]) <= b:
		j += 1
	ans += r(j - i - 2)
	i += 1
print(ans)


(n, d) = map(int, input().split())
arr = [int(x) for x in input().split()]
(i, j, c) = (0, 2, 0)
if n < 3:
	print(0)
else:
	while True:
		if i > n - 3 and j >= n - 1:
			break
		elif arr[j] - arr[i] <= d and j < n - 1:
			j += 1
		elif j == n - 1 and arr[j] - arr[i] <= d:
			z = j - i
			c += z * (z - 1) // 2
			i += 1
		else:
			z = j - i - 1
			c += z * (z - 1) // 2
			i += 1
	print(c)


(n, d) = map(int, input().split())
arr = list(map(int, input().split()))
count = 0
for i in range(n - 2):
	l = i + 2
	r = n - 1
	while l <= r:
		mid = l + (r - l) // 2
		if arr[mid] - arr[i] == d:
			r = mid
			break
		if arr[mid] - arr[i] > d:
			r = mid - 1
		else:
			l = mid + 1
	t = r - i
	t = t * (t - 1) // 2
	count += t
print(count)


from sys import stdin, stdout
from collections import Counter
from collections import defaultdict
from math import ceil
from bisect import bisect_left
from bisect import bisect_right
import math
ai = lambda : list(map(int, stdin.readline().split()))
ei = lambda : map(int, stdin.readline().split())
ip = lambda : int(stdin.readline().strip())
(n, k) = ei()
li = ai()
ans = 0
j = 0
for i in range(2, n):
	while li[i] - li[j] > k:
		j += 1
	x = i - j
	ans += x * (x - 1) // 2
print(ans)


class ArrayQueue:
	DEFAULT_CAPACITY = 10

	def __init__(self):
		self._data = [None] * ArrayQueue.DEFAULT_CAPACITY
		self._size = 0
		self._front = 0

	def __len__(self):
		return self._size

	def is_empty(self):
		return self._size == 0

	def first(self):
		if self.is_empty():
			raise Empty('Queue is empty')
		return self._data[self._front]

	def dequeue(self):
		if self.is_empty():
			raise Empty('Queue is empty')
		answer = self._data[self._front]
		self._data[self._front] = None
		self._front = (self._front + 1) % len(self._data)
		self._size -= 1
		return answer

	def enqueue(self, e):
		if self._size == len(self._data):
			self._resize(2 * len(self._data))
		avail = (self._front + self._size) % len(self._data)
		self._data[avail] = e
		self._size += 1

	def _resize(self, cap):
		old = self._data
		self._data = [None] * cap
		walk = self._front
		for k in range(self._size):
			self._data[k] = old[walk]
			walk = (1 + walk) % len(old)
		self._front = 0

	def show(self):
		print(self._data)
from collections import deque
import itertools
temp = []
temp = input().split(' ')
n = int(temp[0])
d = int(temp[1])
temp = []
temp = input().split(' ')
q = ArrayQueue()
q._resize(n)
for x in temp:
	q.enqueue(int(x))
ans = 0
deque = deque()
while q.is_empty() == False:
	deque.append(q.dequeue())
	while deque[-1] - deque[0] > d:
		deque.popleft()
	s = len(deque)
	ans += (s - 1) * (s - 2) // 2
print(ans)


from bisect import bisect_left as bl

def main():
	(n, d) = map(int, input().split())
	x = list(map(int, input().split()))
	ans = 0
	for (i, e) in enumerate(x):
		end = bl(x, e + d)
		if end == len(x):
			end -= 1
		if e + d < x[end]:
			end -= 1
		span = end - i
		if span >= 2:
			ans += span * (span - 1) // 2
	print(ans)
main()


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
(l, r, ans) = (0, 0, 0)
while r < n:
	while a[r] - a[l] > k:
		l += 1
	m = r - l
	ans += m * (m - 1) // 2
	r += 1
print(ans)


(x, y) = map(int, input().split())
a = list(map(int, input().split()))
i = 0
j = 0
s = 0
while i < x:
	f = 0
	while a[j] - a[i] <= y and j < x:
		j += 1
		if j == x:
			f = 1
			break
	p = j - i - 1
	s += p * (p - 1) // 2
	i += 1
	if f:
		j -= 1
print(s)


import bisect
(N, D) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
ans = 0
for i in range(N):
	X = bisect.bisect_left(A, A[i] - D)
	temp = i - X
	ans += max(0, temp * (temp - 1) // 2)
print(ans)


def fact(n):
	if n == 0:
		return 1
	f = n
	for i in range(1, n):
		f *= i
	return f
(n, d) = map(int, input().split())
l = list(map(int, input().split()))
s = 0
e = s + 2
sm = 0
k = 0
while s < n - 2 or e < n:
	if e == n:
		k = e - 1 - s
		sm += k * (k - 1) // 2
		s += 1
	elif l[e] - l[s] <= d:
		e += 1
	else:
		k = e - 1 - s
		if k >= 2:
			sm += k * (k - 1) // 2
			s += 1
		else:
			s += 1
			e += 1
print(sm)


n = input().split()
a = int(n[0])
b = int(n[1])
t = input().split()
c = []
u = 0
if a <= 2:
	print(0)
	exit()
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))


from bisect import bisect_left
(n, d) = map(int, input().split())
points = list(map(int, input().split()))
final = 0
for i in range(len(points) - 2):
	left = bisect_left(points, points[i] + d)
	if left >= len(points) or points[left] != points[i] + d:
		left -= 1
	n = left - i
	x = 1
	for i in range(1, 3):
		x = x * n / i
		n -= 1
	final += x
print(str(final).replace('.0', ''))


def main():
	(n, d) = map(int, input().split())
	ar = sorted(list(map(int, input().split())))
	ans = 0
	l = 0
	r = 1
	k = 0
	while r < n:
		if ar[r] - ar[l] <= d:
			r += 1
			k += 1
			ans += k * (k - 1) // 2
		else:
			l += 1
			k -= 1
	print(ans)
	return 0
main()


(n, d) = map(int, input().split())
arr = list(map(int, input().split()))
total = 0
left = 0
for right in range(2, n):
	while arr[left] + d < arr[right]:
		left += 1
	x = right - left - 1
	total += (x + 1) * x // 2
print(total)


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


(n, d) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
if n < 3:
	print(0)
else:
	i = 0
	j = 2
	count = 0
	while i < len(arr):
		while j < len(arr) and arr[j] - arr[i] <= d:
			j += 1
		count += (j - i - 1) * (j - i - 2) // 2
		i += 1
	print(count)


import random, math
from copy import deepcopy as dc
from bisect import bisect_left, bisect_right

def randomNumber(s, e):
	return random.randint(s, e)

def randomArray(s, e, s_size, e_size):
	size = random.randint(s_size, e_size)
	arr = [randomNumber(s, e) for i in range(size)]
	return arr

def testcase():
	pass

def brute():
	pass

def effe():
	pass

def solution(li, b):
	if len(li) < 3:
		return 0
	li.sort()
	i = 0
	j = 2
	tot = 0
	while j < len(li):
		while i <= j and li[j] - li[i] > b:
			i += 1
		choices = j - i
		tot += choices * (choices - 1) // 2
		j += 1
	return tot

def input_test():
	(a, b) = map(int, input().strip().split(' '))
	li = list(map(int, input().strip().split(' ')))
	out = solution(li, b)
	print(out)

def test():
	pass
input_test()


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


from sys import stdin
from bisect import bisect_right

def make_dict(arr):
	mydict = dict()
	for i in arr:
		mydict[i] = True
	return mydict

def combi(n, c):
	return n * (n - 1) // 2
(n, d) = list(map(int, stdin.readline().split()))
arr = list(map(int, stdin.readline().split()))
mydict = make_dict(arr)
count = 0
for i in range(n):
	index = bisect_right(arr, arr[i] + d)
	count += combi(index - i - 1, 2)
print(count)


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)


def main():
	(n, d) = (int(inp) for inp in input().split())
	coords = [int(coord) for coord in input().split()]
	groups_points = 0
	for i in range(0, n - 2):
		find = coords[i] + d
		index = binary_search(find, coords, i, n - 1)
		aux = index - i
		groups_points += aux * (aux - 1) // 2
	print(groups_points)
	return groups_points

def binary_search(num, coords, start, end):
	if end <= start:
		if num == coords[start]:
			return start
		else:
			index = start
			while coords[index] > num:
				index -= 1
			return index
	else:
		middle = (end + start) // 2
		if coords[middle] == num:
			return middle
		elif coords[middle] > num:
			return binary_search(num, coords, start, middle - 1)
		else:
			return binary_search(num, coords, middle + 1, end)
main()


(n, d) = map(int, input().split())
if n < 3:
	print(0)
	quit()
f = list(map(int, input().split()))
from collections import deque
g = deque([f[0], f[1]])
num = 0
for i in range(2, n):
	if f[i] - g[0] <= d:
		g.append(f[i])
		num += (len(g) - 1) * (len(g) - 2) // 2
	else:
		while f[i] - g[0] > d:
			g.popleft()
			if len(g) == 0:
				break
		g.append(f[i])
		num += (len(g) - 1) * (len(g) - 2) // 2
print(num)


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


class Deque:

	def __init__(self):
		self.items = []

	def isEmpty(self):
		return self.items == []

	def addFront(self, item):
		self.items.append(item)

	def addRear(self, item):
		self.items.insert(0, item)

	def removeFront(self):
		return self.items.pop()

	def removeRear(self):
		return self.items.pop(0)

	def size(self):
		return len(self.items)

	def front(self):
		return self.items[len(self.items) - 1]

	def last(self):
		return self.items[0]

def groups(num, max, list):
	total = 0
	front = 0
	last = 0
	while last < num - 1:
		for i in range(last + 1, num):
			if list[i] <= list[front] + max:
				last += 1
			else:
				break
		total = (last - front - 1) * (last - front) / 2 + total
		front += 1
		if last < front:
			last += 1
	while front <= last:
		total = (last - front - 1) * (last - front) / 2 + total
		front += 1
	return int(total)
first = input().split(' ')
second = input().split(' ')
first2 = []
second2 = []
for i in first:
	first2.append(int(i))
for i in second:
	second2.append(int(i))
print(groups(first2[0], first2[1], second2))


(n, d) = map(int, input().split())
arr = [*map(int, input().split())]
ans = 0
from bisect import bisect
for i in range(n):
	p = bisect(arr, arr[i] + d) - i - 1
	ans += p * (p - 1) // 2
print(ans)


(n, d) = map(int, input().split())
a = list(map(int, input().split())) + [1000000000000]
ans = 0
l = 0
r = 0
while l < n - 1:
	while a[r] - a[l] <= d:
		r += 1
	ans += (r - l - 1) * (r - l - 2) // 2
	l += 1
print(ans)


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

def find(arr, ind, d):
	start = ind
	end = len(arr) - 1
	if abs(arr[end] - arr[ind]) <= d:
		return len(arr) - 1
	while start + 1 < end:
		mid = (start + end) // 2
		if abs(arr[mid] - arr[ind]) > d:
			end = mid
			continue
		else:
			start = mid
	if abs(arr[end] - arr[ind]) <= d:
		return end
	return start
ans = 0
for i in range(len(arr) - 2):
	k = find(arr, i, d)
	x = k - i
	ans += x * (x - 1) // 2
print(ans)


import heapq
from bisect import bisect_left, bisect_right
from itertools import accumulate
R = lambda : map(int, input().split())
(n, k) = R()
cs = list(R())
(r, res) = (0, 0)
for l in range(n):
	r = bisect_right(cs, cs[l] + k)
	res += (r - l - 1) * (r - l - 2) // 2 if r - l > 2 else 0
print(res)


(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)


import sys
input = sys.stdin.readline
(n, d) = map(int, input().split())
a = list(map(int, input().split()))
triangle = lambda n: n * (n + 1) // 2
res = 0
(l, r) = (0, 1)
one_less = n - 1
while l < n and r < n:
	while r < one_less and a[r + 1] - a[l] <= d:
		r += 1
	if l < r:
		res += triangle(r - l - 1)
	l += 1
print(res)


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
ans = 0
j = 0
for i in range(n):
	while l[i] - l[j] > k:
		j += 1
	total = i - j
	ans += total * (total - 1) // 2
print(ans)


(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)


import bisect
(n, d) = map(int, input().split())
s = 0
l = [int(s) for s in input().split()]
for i in range(n - 2):
	k = l[i] + d
	k1 = 0
	k1 = bisect.bisect_right(l, k)
	if k1 > i:
		k1 = k1 - i - 1
		s += k1 * (k1 - 1) // 2
	else:
		break
print(s)


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


(n, d) = map(int, input().split())
x = list(map(int, input().split()))
(a, b) = (0, 1)
done = 0

def comb(n, r):
	ret = 1
	for i in range(n - r + 1, n + 1):
		ret *= i
	den = 1
	while r > 0:
		den *= r
		r -= 1
	return int(ret / den)

def output(a, b, done):
	ret = 0
	if a < done < b:
		first = done - a
		second = b - done
		ret = comb(first, 2) * comb(second, 1) + comb(first, 1) * comb(second, 2) + comb(second, 3)
	elif b > done:
		check = b - a
		ret = comb(check, 3)
	return ret
ans = 0
while b < n:
	if x[b] - x[a] > d:
		ans += output(a, b, done)
		done = b
		a += 1
	else:
		b += 1
ans += output(a, b, done)
print(ans)


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

def find_match(p, left, right, target):
	right = n - 1
	while left < right:
		middle = (left + right) // 2
		if p[middle] > target:
			right = middle
		else:
			left = middle + 1
	if p[left] <= target:
		left += 1
	return left - 1

def count_sum_one_to(num):
	return int(num * (num + 1) / 2)

def run():
	result = 0
	for i in range(n):
		matched_index = find_match(points, i, n - 1, points[i] + d)
		if i == matched_index:
			continue
		result += count_sum_one_to(matched_index - i - 1)
	return result
print(run())


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


from bisect import bisect_left

def sol(a, n, d):
	ans = 0
	for i in range(n - 2):
		x = a[i] + d
		pos = bisect_left(a, x)
		if pos < n and a[pos] == x:
			pos += 1
		x = pos - (i + 2)
		ans += x * (x + 1) // 2
	return ans
(n, d) = map(int, input().split())
a = [int(i) for i in input().split()]
print(sol(a, n, d))


(n, d) = map(int, input().split())
points = [i for i in map(int, input().split())]
i = 0
j = 2
count = 0

def binary_max(list, left, right, target):
	hi = right
	lo = left
	max = list[lo]
	ind = left
	while lo <= hi:
		mid = (hi + lo) // 2
		midval = list[mid]
		if midval > target:
			hi = mid - 1
		elif midval < target:
			if midval > max:
				max = midval
				ind = mid
			lo = mid + 1
		else:
			ind = mid
			break
	return ind
for i in range(n - 2):
	max = points[i] + d
	end = binary_max(points, i, n - 1, max)
	m = end - i
	count += int((m - 1) * m / 2)
print(count)


(n, d) = map(int, input().split())
a = tuple(map(int, input().split()))
i = 0
s = 0
for j in range(n):
	while a[j] - a[i] > d:
		i += 1
	s += (j - i - 1) * (j - i) // 2
print(s)


(n, m) = map(int, input().split())
ar = sorted(map(int, input().split()))
(res, b, e) = (0, 0, 0)
while e < n - 1:
	e += 1
	while ar[e] - ar[b] > m:
		b += 1
	res += (e - b) * (e - b - 1) >> 1
print(res)


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


from sys import stdin
from bisect import *
from math import factorial

def nCr(n, r):
	(f, m) = (factorial, 1)
	for i in range(n, n - r, -1):
		m *= i
	return int(m // f(r))

def arr_inp(n):
	if n == 1:
		return [int(x) for x in stdin.readline().split()]
	elif n == 2:
		return [float(x) for x in stdin.readline().split()]
	else:
		return [str(x) for x in stdin.readline().split()]
(n, d) = arr_inp(1)
(a, ans) = (arr_inp(1), 0)
for i in range(2, n):
	en = bisect_left(a, a[i] - d)
	ans += nCr(i - en, 2)
print(ans)


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

def bs_last_lesser(arr, start, end, val):
	if start > end:
		return -1
	mid = (start + end) // 2
	if arr[mid] < val:
		if mid == end:
			return mid
		elif arr[mid + 1] >= val:
			return mid
		else:
			return bs_last_lesser(arr, mid + 1, end, val)
	else:
		return bs_last_lesser(arr, start, mid - 1, val)
ans = 0
for i in range(n):
	curr = arr[i]
	index = bs_last_lesser(arr, 0, n - 1, curr + d + 1)
	if index != -1:
		tochoose = index - i
		if tochoose > 1:
			ans += tochoose * (tochoose - 1) // 2
print(ans)


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

def count_sum_one_to(num):
	return int(num * (num + 1) / 2)

def next_index(i, start=0):
	for k in range(start, n):
		if points[k] - d > points[i]:
			return k - 1
	return n - 1
result = 0
(left, right) = (0, 0)
while left < n:
	right = next_index(left, right)
	if left != right:
		result += count_sum_one_to(right - left - 1)
	left += 1
print(result)


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
if n < 3:
	print(0)
else:
	i = 0
	j = n - 1
	count = 0
	while i < n - 2:
		while a[j] - a[i] > d and j - 1 >= i:
			j = j - 1
		count = count + (j - i - 1) * (j - i) // 2
		i = i + 1
		while a[j] - a[i] <= d and j + 1 < n:
			j = j + 1
	print(count)


def main():
	(num, choose) = list(map(int, str(input()).split(' ')))
	array = list(map(int, str(input()).split(' ')))
	(res, j) = (0, 0)
	for (index, element) in enumerate(array):
		while element - array[j] > choose:
			j += 1
		res += int((index - j) * (index - j - 1) / 2)
	print(res)
main()


(n, d) = list(map(int, input().split()))
list1 = list(map(int, input().split()))
l = len(list1)
(i, j, ans) = (0, 0, 0)
while i < n:
	while (list1[i] - list1[j] <= d) == False:
		j += 1
	ans += (i - j) * (i - j - 1) / 2
	i += 1
print(int(ans))


import sys
import math

def bc(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return res

def main():
	q = []
	for line in sys.stdin.readlines():
		q.append(line)
	for i in range(len(q)):
		q[i] = q[i].rstrip().split(' ')
		q[i] = [int(x) for x in q[i]]
	n = q[0][0]
	d = q[0][1]
	a = q[1]
	i = 0
	j = 1
	n_vals = []
	count = 1
	ret = 0
	while i < len(a):
		while j < len(a) and a[i] + d >= a[j]:
			if count >= 2:
				ret += bc(count, 2)
			count += 1
			j += 1
		i += 1
		count = max(count - 1, 1)
		if i == j:
			j += 1
	print(int(ret))
main()


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


from collections import deque
(n, d) = tuple(map(int, input().split()))
coo = deque(map(int, input().split()))
if len(coo) >= 3:
	t = deque([coo.popleft() for i in range(2)])
	count = 0
	while len(coo) != 0:
		t.append(coo.popleft())
		while t[-1] - t[0] > d and len(t) > 2:
			t.popleft()
		count += int(0.5 * (len(t) - 1) * (len(t) - 2))
	print(count)
else:
	print(0)


from collections import deque
from math import factorial
nd = input()
nd = nd.split()
n = int(nd[0])
d = int(nd[1])
xcorr = list(map(int, input().split()))
dq = deque()
g = 0
for x in xcorr:
	dq.append(x)
	while x - dq[0] > d:
		if len(dq) >= 4:
			g += (len(dq) - 2) * (len(dq) - 2 - 1) / 2
		dq.popleft()
if len(dq) >= 3:
	g += len(dq) * (len(dq) - 1) * (len(dq) - 2) / 2 / 3
print(int(g))


(N, target) = input().split()
N = int(N)
target = int(target)
a = [int(i) for i in input().split()]

def checkIdx(a, l, val):
	if a[l] - val > target:
		return -1
	r = len(a) - 1
	while l <= r:
		mid = (l + r) // 2
		if a[mid] - val > target:
			r = mid - 1
		elif a[mid] - val < target:
			l = mid + 1
		else:
			return mid
	return r
i = 0
j = 2
count = 0
while i < N - 2:
	pos = checkIdx(a, j, a[i])
	if pos != -1:
		pos = pos - i - 1
	count += pos * (pos + 1) // 2
	i += 1
	j += 1
print(count)


(n, d) = list(map(int, input().split()))
array = list(map(int, input().split()))
start = 0
end = 0
ans = 0
while end < n:
	while array[end] - array[start] > d:
		start += 1
	k = end - start
	ans += k * (k - 1) // 2
	end += 1
print(ans)


mod = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
from bisect import *
(n, d) = f()
l = il()
c = 0
for i in range(n):
	x = bisect_right(l, l[i] + d)
	c += max(0, (x - i - 2) * (x - i - 1) // 2)
print(c)


(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)


from collections import deque

def group_number(n, d, x):
	D = deque()
	N = 0
	for i in range(0, n):
		D.append(x[i])
		if len(D) < 3:
			continue
		if D[-1] - D[0] <= d:
			N += int((len(D) - 1) * (len(D) - 2) / 2)
		else:
			while D[-1] - D[0] > d:
				D.popleft()
			if len(D) >= 3:
				N += int((len(D) - 1) * (len(D) - 2) / 2)
	return N
str1 = input().split()
n = int(str1[0])
d = int(str1[1])
str2 = input().split()
x = []
for i in range(n):
	x.append(int(str2[i]))
print(group_number(n, d, x))


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


def nCr(n):
	return (n - 1) * n / 2
s = 0
(n, d) = map(int, input().split())
a = list(map(int, input().split()))
l = 1
for i in range(n - 2):
	now = a[i]
	while l < n and a[l] <= now + d:
		l += 1
	if l - i >= 3:
		s += nCr(l - i - 1)
print(int(s))


from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b
S1 = 'abcdefghijklmnopqrstuvwxyz'
S2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
(n, d) = mp()
arr = lmp()
(i, j) = (0, 0)
ans = 0
while i < n:
	while j < n and arr[j] - arr[i] <= d:
		j += 1
	ans += (j - i - 1) * (j - i - 2) // 2
	i += 1
print(ans)


(n, d) = map(int, input().split())
from bisect import bisect_right as bl
(a, r) = (list(map(int, input().split())), 0)
for i in range(n):
	q = bl(a, a[i] + d) - 2 - i
	if q > 0:
		r += q * (q + 1) // 2
print(r)


(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)


def binary_search(arr, n, key):
	(l, r) = (0, n - 1)
	while l <= r:
		mid = l + r >> 1
		if arr[mid] <= key:
			l = mid + 1
		else:
			r = mid - 1
	return l

def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	res = 0
	for i in range(n):
		j = binary_search(a, n, a[i] + k) - i - 2
		res += max(0, j * (j + 1) // 2)
	print(res)
main()


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
(n, d) = value()
a = array()
ans = 0
for i in range(n):
	ind = bisect_right(a, a[i] + d) - 1
	candidates = ind - i
	ans += candidates * (candidates - 1) // 2
print(ans)


from sys import stdin, stdout, stderr

def binary(lo, hi, value):
	global a
	ans = lo
	while lo <= hi:
		mid = (lo + hi) // 2
		if a[mid] <= value:
			ans = mid
			lo = mid + 1
		else:
			hi = mid - 1
	return ans
(n, d) = map(int, input().split())
a = [int(x) for x in input().split()]
ans = 0
for i in range(n):
	lo = binary(i + 1, n - 1, a[i] + d)
	lo = lo - i
	ans = ans + lo * (lo - 1) / 2
print(int(ans))


import bisect
(n, d) = list(map(int, input().split()))
l = list(map(int, input().split()))
s = [0]
for i in range(1, n):
	s.append(s[-1] + l[i] - l[i - 1])
ans = 0
for i in range(n):
	j = bisect.bisect_right(s, d + s[i]) - 1
	if j > i + 1:
		j = j - (i + 1)
		ans = ans + j * (j + 1) // 2
print(ans)


import sys
import string
import math
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache
from fractions import Fraction

def mi(s):
	return map(int, s.strip().split())

def lmi(s):
	return list(mi(s))

def tmi(s):
	return tuple(mi(s))

def mf(f, s):
	return map(f, s)

def lmf(f, s):
	return list(mf(f, s))

def js(lst):
	return ' '.join((str(d) for d in lst))

def jsns(lst):
	return ''.join((str(d) for d in lst))

def line():
	return sys.stdin.readline().strip()

def linesp():
	return line().split()

def iline():
	return int(line())

def mat(n):
	matr = []
	for _ in range(n):
		matr.append(linesp())
	return matr

def matns(n):
	mat = []
	for _ in range(n):
		mat.append([c for c in line()])
	return mat

def mati(n):
	mat = []
	for _ in range(n):
		mat.append(lmi(line()))
	return mat

def pmat(mat):
	for row in mat:
		print(js(row))

def main():
	(_, d) = mi(line())
	arr = lmi(line())
	begin = 0
	ans = 0
	for (e, n) in enumerate(arr):
		while n - arr[begin] > d:
			begin += 1
		elems = e - begin + 1
		if elems < 3:
			continue
		else:
			ans += (elems - 1) * (elems - 2) // 2
	print(ans)
main()


(n, d) = map(int, input().split())
l = list(map(int, input().split()))
i = n - 2
j = n - 1
ans = 0
while j >= 0:
	if i >= 0 and l[j] - l[i] <= d:
		i -= 1
	else:
		k = j - i - 1
		ans += k * (k - 1) // 2
		j -= 1
print(ans)


try:

	def comb(n):
		return n * (n - 1) // 2
	(N, d) = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	l = 0
	ans = 0
	for r in range(2, N):
		while nums[r] - nums[l] > d:
			l += 1
		ans += comb(r - l)
	print(ans)
except Exception as e:
	print(e)


(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
	x = x + (t - i - 1) * (t - i - 2) / 2
print(int(x))


from collections import deque
str1 = input()
str2 = input()
n = int(str1.split()[0])
d = int(str1.split()[1])
numlist = str2.split()
newdeque = deque()
Sum = 0
cha = 0
way = 0
for i in range(n):
	numlist[i] = int(numlist[i])
for i in range(n - 1):
	cha = numlist[i + 1] - numlist[i]
	newdeque.append(cha)
	Sum += cha
	while Sum > d and len(newdeque) != 0:
		Sum -= newdeque.popleft()
	if len(newdeque) > 1:
		way += (len(newdeque) - 1) * len(newdeque) / 2
print(int(way))


def readLine():
	return list(map(int, input().split()))

def lower_bound(arr, el):
	res = -1
	lo = 0
	hi = len(arr) - 1
	while lo <= hi:
		mid = (lo + hi) // 2
		if arr[mid] <= el:
			res = mid
			lo = mid + 1
		else:
			hi = mid - 1
	return res
(n, d) = readLine()
arr = readLine()
res = 0
for (i, x) in enumerate(arr):
	end = lower_bound(arr, x + d)
	k = end - i
	res += k * (k - 1) // 2
print(res)


import bisect
(n, k) = map(int, input().split(' '))
c = [int(x) for x in input().split(' ')]
a = 0
for i in range(n - 2):
	j = bisect.bisect_right(c, c[i] + k)
	a += 0.5 * (j - i - 2) * (j - i - 1)
print(int(a))


import bisect
(n, d) = map(int, input().split())
arr = list(map(int, input().split()))
ans = 0
i = 0
j = 0
while i < n:
	j = bisect.bisect(arr, arr[i] + d, i, n)
	f = j - i - 1
	ans += max(0, f * (f - 1) // 2)
	i += 1
print(ans)


def nCr(n):
	return (n - 1) * n / 2
s = 0
(n, d) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n - 2):
	now = a[i]
	l = i + 1
	r = n - 1
	while r > l:
		c = (r + l) // 2 + 1
		if a[c] > now + d:
			r = c - 1
		else:
			l = c
	if l - i >= 2:
		s += nCr(l - i)
print(int(s))


import sys

def solve(d, points):
	pointer1 = 0
	pointer2 = 0
	totalPairs = 0
	while pointer1 < len(points) - 1:
		if pointer2 < len(points) and abs(points[pointer2] - points[pointer1]) <= d:
			pointer2 += 1
		elif pointer2 == len(points) or abs(points[pointer2] - points[pointer1]) > d:
			nodes = pointer2 - pointer1
			if nodes >= 3:
				nodes -= 1
				pairings = nodes * (nodes - 1) // 2
				totalPairs += pairings
			pointer1 += 1
	return totalPairs

def readinput():
	(n, d) = map(int, sys.stdin.readline().rstrip().split(' '))
	points = list(map(int, sys.stdin.readline().rstrip().split(' ')))
	print(solve(d, points))
readinput()


def solve(n, d, ar):
	ans = 0
	for i in range(n - 1, 1, -1):
		rightmost = i
		p = i - 2
		if ar[rightmost] - ar[p] > d:
			continue
		else:
			l = 0
			r = p
			while l <= r:
				mid = (l + r) // 2
				if ar[rightmost] - ar[mid] > d:
					l = mid + 1
				else:
					r = mid - 1
			if ar[rightmost] - ar[mid] > d:
				k = mid + 1
			else:
				k = mid
			ans += (rightmost - k) * (rightmost - k - 1) // 2
	print(ans)
(n, d) = map(int, input().split())
ar = list(map(int, input().split()))
solve(n, d, ar)


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


ans = 0
(n, x) = map(int, input().split(' '))
lst = list((int(x) for x in input().split(' ')))
j = 2
for i in range(0, n - 2):
	b = 0
	for k in range(j, n):
		if lst[k] - lst[i] > x:
			b = k - 1
			j = k
			break
		else:
			b = k
			j = k
	z = b - (i + 1)
	if b != 0:
		ans += z * (z + 1) / 2
print(int(ans))


import bisect as bs

def main():
	(n, d) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	res = 0
	a.append(a[len(a) - 1] + 1)
	for i in range(n):
		lwb = bs.bisect_right(a, a[i] + d, lo=i, hi=n)
		amount = lwb - i
		if amount >= 3:
			res += (amount - 1) * (amount - 2) // 2
	print(res)
main()


def main():
	(n, d) = [int(x) for x in input().split()]
	pontos = [int(x) for x in input().split()]
	print(solve(n, d, pontos))

def solve(n, d, pontos):
	posib = 0
	comb_2 = lambda n: n * (n - 1) // 2
	for i in range(len(pontos)):
		max_p3 = pontos[i] + d
		i_max_p3 = limite_p3(pontos, max_p3)
		num_elem = i_max_p3 - i
		if num_elem < 1:
			continue
		posib += comb_2(num_elem)
	return posib

def limite_p3(pontos, x):
	l_sup = len(pontos) - 1
	l_inf = 0
	pos = []
	while l_inf <= l_sup:
		meio = l_inf + (l_sup - l_inf) // 2
		if pontos[meio] > x:
			l_sup = meio - 1
		elif pontos[meio] == x:
			return meio
		else:
			l_inf = meio + 1
			pos.append(meio)
	return max(pos)
main()


(n, d) = list(map(int, input().split()))
xs = list(map(int, input().split()))
xs.sort()
i = 0
j = 1
ans = 0
for i in range(n):
	while j < len(xs) and xs[j] - xs[i] <= d:
		j += 1
	if xs[j - 1] - xs[i] <= d and j - i >= 3:
		ans += (j - i - 1) * (j - i - 2) // 2
print(ans)


from __future__ import division, print_function
import math
import os
import sys
from fractions import *
from sys import *
from decimal import *
from io import BytesIO, IOBase
from itertools import *
from collections import *
M = 10 ** 9 + 7
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def inpu():
	return int(inp())

def regularbracket(t):
	p = 0
	for i in t:
		if i == '(':
			p += 1
		else:
			p -= 1
		if p < 0:
			return False
	else:
		if p > 0:
			return False
		else:
			return True

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def reverse1(string):
	pp = ''
	for i in string[::-1]:
		pp += i
	if pp == string:
		return True
	return False

def reverse2(list1):
	l = []
	for i in list1[::-1]:
		l.append(i)
	if l == list1:
		return True
	return False

def mex(list1):
	p = max(list1) + 1
	for i in range(len(list1)):
		if list1[i] != i:
			p = i
			break
	return p

def sumofdigits(n):
	n = str(n)
	s1 = 0
	for i in n:
		s1 += int(i)
	return s1

def perfect_square(n):
	s = math.sqrt(n)
	if s == int(s):
		return True
	return False

def roman_number(x):
	if x > 15999:
		return
	value = [5000, 4000, 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
	symbol = ['F', 'MF', 'M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I']
	roman = ''
	i = 0
	while x > 0:
		div = x // value[i]
		x = x % value[i]
		while div:
			roman += symbol[i]
			div -= 1
		i += 1
	return roman

def soretd(s):
	for i in range(1, len(s)):
		if s[i - 1] > s[i]:
			return False
	return True

def countRhombi(h, w):
	ct = 0
	for i in range(2, h + 1, 2):
		for j in range(2, w + 1, 2):
			ct += (h - i + 1) * (w - j + 1)
	return ct

def countrhombi2(h, w):
	return h * h // 4 * (w * w // 4)

def binpow(a, b):
	if b == 0:
		return 1
	else:
		res = binpow(a, b // 2)
	if b % 2 != 0:
		return res * res * a
	else:
		return res * res

def binpowmodulus(a, b, m):
	a %= m
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % m
		a = a * a % m
		b >>= 1
	return res

def coprime_to_n(n):
	result = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
			result -= result // i
		i += 1
	if n > 1:
		result -= result // n
	return result

def prime(x):
	if x == 1:
		return False
	else:
		for i in range(2, int(math.sqrt(x)) + 1):
			if x % i == 0:
				return False
		else:
			return True

def luckynumwithequalnumberoffourandseven(x, n, a):
	if x >= n and str(x).count('4') == str(x).count('7'):
		a.append(x)
	elif x < 1000000000000.0:
		luckynumwithequalnumberoffourandseven(x * 10 + 4, n, a)
		luckynumwithequalnumberoffourandseven(x * 10 + 7, n, a)
	return a

def luckynuber(x, n, a):
	p = set(str(x))
	if len(p) <= 2:
		a.append(x)
	if x < n:
		luckynuber(x + 1, n, a)
	return a

def interact(type, x):
	if type == 'r':
		inp = input()
		return inp.strip()
	else:
		print(x, flush=True)

def findTrailingZeros(n):
	count = 0
	while n >= 5:
		n //= 5
		count += n
	return count

def mergeSort(arr):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		mergeSort(L)
		mergeSort(R)
		i = j = k = 0
		while i < len(L) and j < len(R):
			if L[i] < R[j]:
				arr[k] = L[i]
				i += 1
			else:
				arr[k] = R[j]
				j += 1
			k += 1
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1
res = set()

def solven(p, l, a, b, n):
	if p > n or l > 10:
		return
	if p > 0:
		res.add(p)
	solven(p * 10 + a, l + 1, a, b, n)
	solven(p * 10 + b, l + 1, a, b, n)

def subsetsUtil(A, subset, index, d):
	print(*subset)
	s = sum(subset)
	d.append(s)
	for i in range(index, len(A)):
		subset.append(A[i])
		subsetsUtil(A, subset, i + 1, d)
		subset.pop(-1)
	return d

def subsetSums(arr, l, r, d, sum=0):
	if l > r:
		d.append(sum)
		return
	subsetSums(arr, l + 1, r, d, sum + arr[l])
	subsetSums(arr, l + 1, r, d, sum)
	return d

def print_factors(x):
	factors = []
	for i in range(1, x + 1):
		if x % i == 0:
			factors.append(i)
	return factors

def calc(X, d, ans, D):
	if len(X) == 0:
		return
	i = X.index(max(X))
	ans[D[max(X)]] = d
	Y = X[:i]
	Z = X[i + 1:]
	calc(Y, d + 1, ans, D)
	calc(Z, d + 1, ans, D)

def factorization(n, l):
	c = n
	if prime(n) == True:
		l.append(n)
		return l
	for i in range(2, c):
		if n == 1:
			break
		while n % i == 0:
			l.append(i)
			n = n // i
	return l

def good(b):
	l = []
	i = 0
	while len(b) != 0:
		if b[i] < b[len(b) - 1 - i]:
			l.append(b[i])
			b.remove(b[i])
		else:
			l.append(b[len(b) - 1 - i])
			b.remove(b[len(b) - 1 - i])
	if l == sorted(l):
		return True
	return False

def generate(st, s):
	if len(s) == 0:
		return
	if s not in st:
		st.add(s)
		for i in range(len(s)):
			t = list(s).copy()
			t.remove(s[i])
			t = ''.join(t)
			generate(st, t)
	return

def largestincreasingsubsequence(A):
	l = [1] * len(A)
	sub = []
	for i in range(1, len(l)):
		for k in range(i):
			if A[k] < A[i]:
				sub.append(l[k])
		l[i] = 1 + max(sub, default=0)
	return max(l, default=0)

def findOR(nums, N):
	prefix_sum = 0
	result = 0
	for i in range(N):
		result |= nums[i]
		prefix_sum += nums[i]
		result |= prefix_sum
	return result

def OR(a, n):
	ans = a[0]
	for i in range(1, n):
		ans |= a[i]
	return ans

def main():
	(n, d) = sep()
	arr = lis()
	arr += [1e+16]
	a = i = j = 0
	while i < n - 1:
		while arr[j] - arr[i] <= d:
			j += 1
		a += (j - i - 1) * (j - i - 2) // 2
		i += 1
	print(a)
main()


from bisect import bisect_left
inp = input().split(' ')
n = int(inp[0])
d = int(inp[1])
arr = [int(x) for x in input().split(' ')]
ans = 0
for i in range(len(arr)):
	x = arr[i]
	upper = x - d
	k = max(i - bisect_left(arr, upper, 0, len(arr)), 0)
	ans += k * (k - 1) / 2
print(int(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()


import math
import sys
import collections
import bisect
import string
import time

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
for t in range(1):
	(n, d) = get_ints()
	arr = get_list()
	ans = 0
	for i in range(n - 2):
		starting = arr[i]
		start_point = i
		maxim = starting + d
		extreme_point = bisect.bisect_right(arr, maxim)
		end_point = extreme_point - 1
		gap = end_point - start_point
		ans += gap * (gap - 1) // 2
	print(ans)


def BS(low, high, key, l):
	ans = 0
	while low <= high:
		mid = (low + high) // 2
		if l[mid] == key:
			floor = key
			ans = mid
			break
		elif l[mid] < key:
			floor = l[mid]
			ans = mid
			low = mid + 1
		elif l[mid] > key:
			high = mid - 1
	return ans
(n, k) = map(int, input().split())
l = [int(i) for i in input().split()]
aa = 0
for i in range(len(l) - 2):
	e = BS(i, len(l) - 1, l[i] + k, l)
	length = e - i + 1
	aa += (length - 2) * (length - 1) // 2
print(aa)


from bisect import bisect_right
(n, d) = map(int, input().split())
a = list(map(int, input().split()))
res = 0
for i in range(n - 2):
	j = bisect_right(a, a[i] + d)
	k = j - i
	res += (k - 1) * (k - 2) // 2
print(res)


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
res = 0
left = 0
for right in range(n):
	while a[right] - a[left] > d:
		left += 1
	x = right - left
	res += int(x * (x - 1) / 2)
print(res)


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
l = 0
ans = 0
for i in range(n):
	while abs(a[i] - a[l]) > d:
		l = l + 1
	len = i - l - 1
	if len > 0:
		ans = ans + len * (len + 1) // 2
print(ans)


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
left = 0
right = 0
ans = 0
while right < n:
	while arr[right] - arr[left] > k:
		left += 1
	m = right - left
	ans += m * (m - 1) // 2
	right += 1
print(ans)


import bisect
(n, d) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
ans = 0
for i in range(0, n):
	x = bisect.bisect_right(a, a[i] + d)
	ans += (x - i - 1) * (x - i - 2) // 2
print(ans)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass

def pmat(A):
	for ele in A:
		print(*ele, end='\n')

def seive():
	prime = [1 for i in range(10 ** 6 + 1)]
	prime[0] = 0
	prime[1] = 0
	for i in range(10 ** 6 + 1):
		if prime[i]:
			for j in range(2 * i, 10 ** 6 + 1, i):
				prime[j] = 0
	return prime
(n, d) = L()
A = L()
ans = 0
for i in range(n):
	x = br(A, A[i] + d)
	x -= 1 if x == n else int(A[x] > A[i] + d)
	f = x - i
	if f < 2:
		continue
	ans += f * (f - 1) // 2
print(ans)
endtime = time.time()


import math
(count, bounds) = [int(x) for x in input().split(' ')]
total = 0
left_index = 0
right_index = 2
current = 0
lst = [int(x) for x in input().split(' ')]
if lst[0] < 0:
	delta = 1 - lst[0]
	lst = [x + delta for x in lst]
while right_index < len(lst):
	if lst[right_index] - lst[left_index] <= bounds:
		right_index += 1
		continue
	elements = right_index - left_index - 1
	total += elements * (elements - 1) / 2
	left_index += 1
while left_index < len(lst) - 2:
	if lst[count - 1] - lst[left_index] <= bounds:
		elements = count - left_index - 2
		total += elements * (elements + 1) / 2
		left_index += 1
print(int(total))


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


(n, k) = map(int, input().split())
list1 = [int(x) for x in input().split()]
flag = False
if n < 3:
	print(0)
else:
	list1.sort()
	i = 0
	j = 2
	total = 0
	while j < len(list1):
		while i <= j and list1[j] - list1[i] > k:
			i += 1
		choices = j - i
		total += choices * (choices - 1) // 2
		j += 1
	print(total)


iarr = list(map(int, input().split()))
n = iarr[0]
d = iarr[1]
arr = list(map(int, input().split()))
arr.sort()
ans = 0
for i in range(n - 2):
	curr = arr[i]
	l = i + 1
	r = n - 1
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] > curr + d:
			r = mid - 1
		else:
			l = mid + 1
	l -= 1
	if l > i:
		count = l - i
		ans += count * (count - 1) // 2
print(ans)


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


def BS(X, z, l, h):
	if l == h:
		return h
	else:
		m = (l + h) // 2
		if z < X[m]:
			return BS(X, z, l, m)
		else:
			return BS(X, z, m + 1, h)
(n, d) = map(int, input().split())
X = list(map(int, input().split()))
i = 0
j = 2
c = 0
while i < n - 2:
	a = X[i] + d
	j = BS(X, a, i + 2, n) - 1
	if a > X[n - 1]:
		j = n - 1
	k = j - i - 1
	c = c + k * (k + 1) // 2
	i = i + 1
print(c)


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


def cnk(n):
	return 0 if 2 > n else n * (n - 1) // 2
(n, d) = input().split()
(n, d) = (int(n), float(d))
dots = list(map(int, input().split()))
(l, r, res) = (0, 0, 0)
while r < n:
	while l < r and dots[r] - dots[l] > d:
		l += 1
	res += cnk(r - l)
	r += 1
print(res)


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

def C(n, k):
	if n < k:
		return 0
	return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))
i = 0
j = 1
cnt = 1
ans = 0
while i < n and j < n:
	if arr[j] - arr[i] > d:
		i += 1
	else:
		cnt = j - i
		j += 1
		ans = ans + cnt * (cnt - 1) // 2
print(ans)


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


import sys
import collections
from collections import Counter, deque
import itertools
import math
import timeit
import random

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=1):
	divisors = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				divisors.append(i)
			else:
				divisors.extend([i, n // i])
	return divisors

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def flin(d, x, default=-1):
	left = right = -1
	for i in range(len(d)):
		if d[i] == x:
			if left == -1:
				left = i
			right = i
	if left == -1:
		return (default, default)
	else:
		return (left, right)

def ceil(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def prr(a, sep=' '):
	print(sep.join(map(str, a)))

def dd():
	return collections.defaultdict(int)

def ddl():
	return collections.defaultdict(list)
(n, m) = mi()
d = li()
i = res = 0
j = i + 2
while i + 2 < n:
	while j < n and d[j] - d[i] <= m:
		j += 1
	k = j - i - 2
	res += k * (k + 1) // 2
	i += 1
print(res)


(n, d) = [int(x) for x in input().split()]
points = [int(p) for p in input().split()]
cnt = 0
first = 0
second = 2
while first < len(points):
	while second < n and points[second] - points[first] <= d:
		second += 1
	diff = second - first - 1
	if diff > 0:
		cnt += diff * (diff - 1) // 2
	first += 1
print(cnt)


(n, k) = list(map(int, input().split()))
arr = list(map(int, input().split()))
if n < 3:
	print(0)
else:
	(ans, i, j) = (0, 0, 2)
	while i < n - 2 and j < n:
		if arr[j] - arr[i] <= k:
			ans += (j - i - 1) * (j - i) // 2
			j += 1
		else:
			i += 1
			if i == j:
				j += 1
	print(ans)


from bisect import bisect_right
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
dsum = i = 0
for i in range(n):
	count = bisect_right(a, a[i] + k) - i
	if count < 3:
		continue
	dsum += (count - 1) * (count - 2) // 2
print(dsum)


import math
import io
(nancy, chim) = map(int, input().split())
alpha = list(map(int, input().split()))
(nano, zen) = (0, 0)
for i in range(nancy):
	while alpha[i] > chim + alpha[zen] and zen < nancy:
		zen += 1
	p = i - zen - 1
	nano += (p + 1) * p // 2
print(nano)


(n, d) = map(int, input().split())
l = list(map(int, input().split())) + [10000000000.0]
a = i = j = 0
while i < n - 1:
	while l[j] - l[i] <= d:
		j += 1
	a += (j - i - 1) * (j - i - 2) // 2
	i += 1
print(a)


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


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])
cnt += comb(len(de)) - comb(temp)
print(cnt)


import math

def sum(a, b):
	n = b - a
	return n * (n - 1) // 2
(n, d) = map(int, input().split())
arr = list(map(int, input().strip().split()))
s = 0
for i in range(n):
	a = arr[i]
	l = 0
	r = n
	while r - l > 1:
		mid = (r + l) // 2
		if arr[mid] - arr[i] > d:
			r = mid
		else:
			l = mid
	if l - i + 1 >= 3:
		s += sum(i + 1, l + 1)
print(s)


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

def find_index(a, l, val):
	if a[l] - val > d:
		return -1
	r = len(a) - 1
	while l <= r:
		mid = (l + r) // 2
		if a[mid] - val > d:
			r = mid - 1
		elif a[mid] - val < d:
			l = mid + 1
		else:
			return mid
	return r
i = 0
j = 2
count = 0
while i < n - 2:
	pos = find_index(a, j, a[i])
	if pos != -1:
		pos = pos - i - 1
	count += pos * (pos + 1) // 2
	i += 1
	j += 1
print(count)


(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)
	exit()
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))


import sys
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()

def calculate(n):
	if n < 1:
		return 0
	return n * (n + 1) // 2
(n, d) = get_ints()
Arr = get_array()
ans = 0
for i in range(n):
	index = bisect_right(Arr, Arr[i] + d)
	ans += calculate(index - i - 2)
print(ans)


from collections import Counter, defaultdict, deque
import math
import sys
input = sys.stdin.readline
(n, d) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
window = deque()
res = 0
for el in arr:
	window.append(el)
	while len(window) >= 1 and window[-1] - window[0] > d:
		window.popleft()
	l = len(window)
	res += (l - 2) * (l - 1) // 2
print(res)


def main():
	(n, d) = read_ints()
	A = read_ints()
	total = 0
	(i, j) = (0, 0)
	for i in range(n):
		while j < n and A[j] - A[i] <= d:
			j += 1
		total += max(0, (j - i - 1) * (j - i - 2) // 2)
	print(total)
from collections import *
MOD = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def read_int():
	return int(input())

def read_ints():
	return list(map(int, input().split()))

def print_nums(nums):
	print(' '.join(map(str, nums)))

def YES():
	print('YES')

def Yes():
	print('Yes')

def NO():
	print('NO')

def No():
	print('No')

def fib(n):
	(a, b) = (0, 1)
	for _ in range(n):
		(a, b) = (b, a + b)
	return a

def fib_ns(n):
	assert n >= 1
	f = [0 for _ in range(n + 1)]
	f[0] = 0
	f[1] = 1
	for i in range(2, n + 1):
		f[i] = f[i - 1] + f[i - 2]
	return f

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b, a % b)

def xgcd(a, b):
	(x0, x1, y0, y1) = (0, 1, 1, 0)
	while a != 0:
		((q, a), b) = (divmod(b, a), a)
		(y0, y1) = (y1, y0 - q * y1)
		(x0, x1) = (x1, x0 - q * x1)
	return (b, x0, y0)

def modinv(a, m):
	(g, x, _) = xgcd(a, m)
	if g != 1:
		raise Exception('gcd(a, m) != 1')
	return x % m

def mod_add(x, y):
	x += y
	while x >= MOD:
		x -= MOD
	while x < 0:
		x += MOD
	return x

def mod_mul(x, y):
	return x * y % MOD

def mod_pow(x, y):
	if y == 0:
		return 1
	if y % 2:
		return mod_mul(x, mod_pow(x, y - 1))
	p = mod_pow(x, y // 2)
	return mod_mul(p, p)

def mod_inv(y):
	return mod_pow(y, MOD - 2)

def mod_div(x, y):
	return mod_mul(x, mod_inv(y))
main()


from bisect import bisect

def binarySearch(arr, x):
	l = 0
	r = len(arr) - 1
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] < x:
			l = mid + 1
		else:
			r = mid - 1
	return r
(n, d) = map(int, input().split())
ls = list(map(int, input().split()))
sm = 0
for i in range(n):
	r = binarySearch(ls, ls[i] + d)
	k = r - i
	sm += k * (k - 1) // 2
print(sm)


from collections import defaultdict

def ncr(n, k):
	C = [[0 for x in range(k + 1)] for x in range(n + 1)]
	for i in range(n + 1):
		for j in range(min(i, k) + 1):
			if j == 0 or j == i:
				C[i][j] = 1
			else:
				C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
	return C[n][k]
(n, k) = map(int, input().split())
a = [int(x) for x in input().split()]
j = 0
ans = 0
for i in range(n):
	while a[i] - a[j] > k:
		j += 1
	ans += (i - j) * (i - j - 1) // 2
print(ans)


(n, d) = list(map(int, input().split()))
x = list(map(int, input().split()))
l = 0
ans = 0
for r in range(n):
	while x[r] - x[l] > d:
		l += 1
	k = max(0, r - l - 1)
	ans += k * (k + 1) // 2
print(ans)


[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)


ar = []
for i in input().split(' '):
	ar.append(int(i))
ar2 = []
for i in input().split(' '):
	ar2.append(int(i))
count = 0
curr = 2
for i in range(len(ar2)):
	temp = curr
	for j in range(temp, len(ar2)):
		if ar2[j] - ar2[i] <= ar[1]:
			curr = j
		else:
			break
	if len(ar2) > curr:
		if ar2[curr] - ar2[i] <= ar[1]:
			count = count + (curr - i) * (curr - i - 1) // 2
print(count)


from bisect import bisect_right
(n, d) = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
for i in range(n):
	j = bisect_right(A, A[i] + d) - 1
	ans += (j - i) * (j - i - 1) // 2
print(ans)


(n, d) = map(int, input().split())
arr = list(map(int, input().split()))
ans = 0
l = 0
for i in range(n):
	while arr[i] - arr[l] > d:
		l += 1
	k = i - l
	ans += k * (k - 1) // 2
print(ans)


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


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


def ncr(n):
	return n * (n - 1) // 2
(n, d) = map(int, input().split())
a = [int(i) for i in input().split()]
l = 0
r = 2
ans = 0
if len(a) < 3:
	print(0)
	exit()
while r != n:
	if a[r] - a[l] > d:
		if r - l > 2:
			l += 1
		else:
			r += 1
	elif a[r] - a[l] <= d:
		ans += ncr(r - l)
		r += 1
print(ans)


(n, d) = map(int, input().split())
p = list(map(int, input().split()))
if n <= 2:
	print(0)
else:
	l = 0
	r = 2
	cnt = 0
	while r < n:
		if p[r] - p[l] <= d:
			r += 1
		else:
			cnt = cnt + (r - l - 1) * (r - l - 2) // 2
			l = l + 1
	while l < n - 2:
		cnt = cnt + (r - l - 1) * (r - l - 2) // 2
		l += 1
	print(cnt)


import sys
input = sys.stdin.readline
(n, d) = map(int, input().split())
a = list(map(int, input().split()))
if n < 3:
	print(0)
	exit()
else:
	i = 0
	j = 1
	c = 0
	while i < n and j < n:
		if a[j] - a[i] <= d:
			if j < n - 1:
				j += 1
			elif j == n - 1:
				l = j - i + 1
				c += (l - 2) * (l - 1) // 2
				i += 1
		else:
			l = j - 1 - i + 1
			c += (l - 2) * (l - 1) // 2
			i += 1
	print(c)


from collections import deque
d = deque()
(n, l) = input().split()
n = int(n)
l = int(l)
s4 = input().split()
for i in range(len(s4)):
	s4[i] = int(s4[i])
s4.append(0)
suma = 0
j = 0
i = 0
x = 0
for i in range(n - 2):
	while j < n and s4[j] - s4[i] <= l:
		d.append(s4[j])
		j += 1
	x += (len(d) - 1) * (len(d) - 2) / 2
	d.popleft()
print(int(x))


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


(n, d) = map(int, input().split(' '))
l = list(map(int, input().split(' ')))
ans = 0
i = 0
j = 0
while n > i:
	while l[i] - l[j] > d:
		j += 1
	ans += (i - j) * (i - j - 1) // 2
	i += 1
print(ans)


e = input()
(n, d) = e.split()
(n, d) = (int(n), int(d))
e = input()
a = [int(x) for x in e.split()]
if n < 3:
	print(0)
else:
	i = 0
	j = 2
	c = 0
	while j < len(a):
		if a[j] - a[i] <= d:
			n = j - i - 1
			c += n * (n + 1) / 2
			j += 1
		else:
			i += 1
	print(int(c))


import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
ans = 0
i = 0
for j in range(n):
	while l[j] - l[i] > m:
		i += 1
	if l[j] - l[i] <= m:
		ans += (j - i) * (j - i - 1) // 2
print(ans)


nd = input()
pieces = nd.split()
n = int(pieces[0])
d = int(pieces[1])
X = input()
x = X.split()
s = 0
kk = 2
for j in range(0, n - 2):
	if int(x[n - 1]) - int(x[j]) <= d:
		s = s + (n - j) * (n - j - 1) * (n - j - 2) / 6
		break
	else:
		for k in range(kk, n):
			if int(x[k]) - int(x[j]) > d:
				kk = k
				s = s + (kk - 1 - j) * (kk - 2 - j) / 2
				break
print(int(s))


(n, dist) = map(int, input().split())
points = list(map(int, input().split()))
group_count = 0
tail = 0
for head in range(n):
	while points[head] - points[tail] > dist:
		tail += 1
	k = head - tail
	group_count += k * (k - 1) // 2
print(group_count)


import sys
input = sys.stdin.readline
read = lambda : map(int, input().split())
read_float = lambda : map(float, input().split())

def ceil(x):
	if x != int(x):
		x = int(x) + 1
	return x

def factorial(x, m):
	val = 1
	while x > 0:
		val = val * x % m
		x -= 1
	return val

def fact(x):
	val = 1
	while x > 0:
		val *= x
		x -= 1
	return val

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // math.gcd(a, b)

def nCr(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	(prime[0], prime[1]) = (False, False)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if n > 1:
		result = result * (1.0 - 1.0 / float(n))
	return int(result)

def is_prime(n):
	if n == 0:
		return False
	if n == 1:
		return True
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True
MAXN = int(100000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
spf = [0 for i in range(MAXN)]

def factoriazation(x):
	res = []
	for i in range(2, int(x ** 0.5) + 1):
		while x % i == 0:
			res.append(i)
			x //= i
	if x != 1:
		res.append(x)
	return res

def factors(n):
	res = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			res.append(i)
			res.append(n // i)
	return list(set(res))

def int_array():
	return list(map(int, input().strip().split()))

def float_array():
	return list(map(float, input().strip().split()))

def str_array():
	return input().strip().split()

def binary_search(low, high, w, h, n):
	while low < high:
		mid = low + (high - low) // 2
		if check(mid, w, h, n):
			low = mid + 1
		else:
			high = mid
	return low

def check(councils, a, k):
	summ = 0
	for x in a:
		summ += min(x, councils)
	return summ // councils >= k
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
from itertools import permutations
import math
import bisect as bis
import random
import sys

def solve():
	(n, d) = read()
	coordinates = list(read())
	m = {}
	s = 0
	for i in range(n - 2):
		a = bis.bisect_right(coordinates, coordinates[i] + d) - i - 2
		s += a * (a + 1) // 2
	print(s)
for _ in range(1):
	solve()


import sys
input = sys.stdin.readline

def inInt():
	return int(input())

def inStr():
	return input().strip('\n')

def inIList():
	return list(map(int, input().split()))

def inSList():
	return input().split()

def solve(case, d):
	ans = 0
	j = 0
	for i in range(len(case)):
		while case[i] - case[j] > d:
			j += 1
		ans += int((i - j) * (i - j - 1) / 2)
	print(ans)
nums = inIList()
case = inIList()
solve(case, nums[1])


import sys
import math as mt
import bisect
input = sys.stdin.buffer.readline

def ncr(n):
	c = 3
	return n * (n - 1) * (n - 2) // 6
t = 1
for __ in range(t):
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 0
	pre = 0
	for i in range(n):
		l1 = bisect.bisect(l, l[i] + d)
		if l1 - i >= 3:
			ans += ncr(l1 - i)
			if pre - i >= 3:
				ans -= ncr(pre - i)
		pre = l1
	print(ans)


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, d) = list(map(int, input().split()))
x = list(map(int, input().split()))
x.append(x[-1] + d + 1)
(s, i, j) = (0, 0, 0)
while i < n - 1:
	while x[j] - x[i] <= d:
		j += 1
	s += (j - i - 1) * (j - i - 2) // 2
	i += 1
print(s)


def c(a, b):
	i = a
	ansc = 1
	while i > a - b:
		ansc = ansc * i
		i = i - 1
	i = 1
	while i <= b:
		ansc = ansc / i
		i = i + 1
	if a < b:
		ansc = 0
	return ansc
(n, d) = input().split(' ')
n = int(n)
d = int(d)
que = input().split(' ')
l = len(que)
i = 0
ans = 0
while i < l:
	que[i] = int(que[i])
	i = i + 1
qbegin = 0
qend = 2
while qend < l:
	test = que[qend] - que[qbegin]
	while test > d and qbegin <= qend:
		qbegin += 1
		test = que[qend] - que[qbegin]
	if qend - qbegin > 1:
		ans = ans + c(qend - qbegin + 1, 3) - c(qend - qbegin, 3)
	qend = qend + 1
print(int(ans))


nd = input().split(' ')
n = int(nd[0])
d = int(nd[1])
a = list(map(int, input().split(' ')))
q = 0

def just_in_at_border(i, k):
	global a
	global d
	global n
	if k == n - 1 and a[k] - a[i] <= d:
		return True
	elif a[k + 1] - a[i] > d and a[k] - a[i] <= d:
		return True
	else:
		return False

def in_range(i, k):
	global a
	global n
	global d
	if a[k] - a[i] <= d:
		return True
	else:
		return False

def increment_count(i, j):
	global q
	if j > i + 1:
		q += round((j - i) * (j - i - 1) / 2)
for i in range(n):
	p1 = i
	p2 = n - 1
	while True:
		k = int((p1 + p2) / 2)
		if k == p1 or k == p2:
			if just_in_at_border(i, p1):
				increment_count(i, p1)
				break
			elif just_in_at_border(i, p2):
				increment_count(i, p2)
				break
		elif just_in_at_border(i, k):
			increment_count(i, k)
			break
		elif in_range(i, k):
			p1 = k + 1
		else:
			p2 = k - 1
print(q)


def main():
	(n, d) = map(int, input().split())
	X = [int(x) for x in input().split()]
	cnt = 0
	for i in range(n):
		l = i
		r = n - 1
		j = -1
		while l <= r:
			m = l + (r - l) // 2
			if X[m] - X[i] <= d:
				l = m + 1
				j = max(j, m)
			else:
				r = m - 1
		if j != -1:
			cnt += (j - i - 1) * (j - i) // 2
	print(cnt)
main()


import bisect
(x, y) = map(int, input('').split())
ar = list(map(int, input('').split()))
ct = 0
for i in range(x):
	z = ar[i] + y
	ind = bisect.bisect_right(ar, z) - 1
	ct = ct + (ind - i) * (ind - i - 1) / 2
print(int(ct))


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) = 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, m) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
ans = 0
i = 0
for j in range(n):
	while l[j] - l[i] > m:
		i += 1
	if l[j] - l[i] <= m:
		ans += (j - i) * (j - i - 1) // 2
print(ans)


def com(n):
	return n * (n - 1) // 2
(n, d) = list(map(int, input().split()))
x = (n + 1) * [0]
x[1:n] = list(map(int, input().split()))
nCount = 0
k = 1
for i in range(3, n + 1):
	while k < i - 1:
		if x[i] - x[k] <= d:
			nCount += com(i - k)
			break
		else:
			k += 1
print(nCount)


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))


(n, k) = map(int, input().split())
t = list(map(int, input().split()))
ans = 0
st = 0
for en in range(n):
	while t[en] - t[st] > k:
		st += 1
	total = en - st
	ans += total * (total - 1) // 2
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(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 foo(x):
	return x * (x - 1) // 2
(n, d) = map(int, input().split())
l = list(map(int, input().split())) + [10000000000.0]
j = 0
c = 0
for i in range(2, n):
	while l[i] - l[j] > d:
		j += 1
	k = i - j
	c = c + foo(k)
print(c)


def bs(num):
	low = 0
	high = n - 1
	while low < high:
		mid = (low + high) // 2
		if a[mid] - num > d:
			high = mid - 1
		else:
			low = mid + 1
	if a[low] - num > d:
		return low - 1
	else:
		return low
(n, d) = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
	f = bs(a[i])
	f = f - i
	ans += max(0, f * (f - 1) // 2)
print(ans)


def bsearch(q, l, first, last):
	if first >= last:
		return first
	else:
		mid = (first + last) // 2
		if q < l[mid]:
			return bsearch(q, l, first, mid)
		elif q > l[mid]:
			return bsearch(q, l, mid + 1, last)
		else:
			return mid
(n, d) = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
ans = 0
for first in range(n - 2):
	last = bsearch(d + l[first], l, 0, n - 1)
	if last - first < 2 or first >= last:
		continue
	if l[last] - l[first] > d:
		last -= 1
	x = last - first - 1
	ans += x * (1 + x) // 2
print(ans)


(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)


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

def bs(ele, left, right):
	best = 1
	while left <= right:
		mid = left + (right - left) // 2
		if abs(ele - mid) < 2:
			left += 1
		elif abs(a[ele] - a[mid]) <= d:
			best = mid
			left = mid + 1
		else:
			right = mid - 1
	return best
cnt = 0
for i in range(n - 2):
	c = bs(i, i, n - 1) - i
	if c >= 2:
		cnt += c * (c - 1) // 2
print(cnt)


(n, d) = map(int, input().split())
a = list(map(int, input().split())) + [int(10000000000.0)]
a.sort()
ans = 0
i = 0
j = 0
while i < n - 1:
	while a[j] - a[i] <= d:
		j += 1
	ans += (j - i - 1) * (j - i - 2) // 2
	i += 1
print(ans)


from sys import stdin
(n, d) = map(int, stdin.readline().strip().split())
x = list(map(int, stdin.readline().strip().split()))
x.sort()
end = 0
cnt = 0
for i in range(len(x)):
	for j in range(end, len(x)):
		if x[j] - x[i] <= d:
			end = j
		else:
			break
	l = end - i
	cnt += l * (l - 1) // 2
print(cnt)


s = [int(i) for i in input().split()]
n = s[0]
k = s[1]
a = [int(i) for i in input().split()]
i = 0
j = 0
total = 0
while i < n:
	while j < n and a[j] - a[i] <= k:
		j += 1
	if j - i >= 3:
		x = j - i - 1
		total += x * (x - 1) / 2
	i += 1
print(int(total))


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)


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
l = 0
res = 0
for r in range(2, n):
	while l + 2 <= r:
		if a[r] - a[l] > d:
			l += 1
		else:
			res += (r - l) * (r - l - 1) // 2
			break
print(res)


def numbersListInput():
	aux = list(map(int, input().strip().split()))
	return aux

def find_tail(arr, n, maxVal):
	mini = 0
	maxi = n
	mid = int(n / 2)
	while True:
		if mid == 0 or mid == n - 1:
			return mid
		if arr[mid] == maxVal:
			return mid
		if arr[mid] > maxVal and arr[mid - 1] < maxVal:
			return mid - 1
		if arr[mid] > maxVal and arr[mid - 1] > maxVal:
			maxi = mid
			mid = int((mini + maxi) / 2)
		if arr[mid] < maxVal and arr[mid - 1] < maxVal:
			mini = mid
			mid = int((mini + maxi) / 2)
usr_input = numbersListInput()
n = int(usr_input[0])
d = int(usr_input[1])
numbersList = numbersListInput()
res = 0
tail = 0
for head in range(n):
	while numbersList[head] - numbersList[tail] > d:
		tail += 1
	res += int((head - tail) * (head - tail - 1) / 2)
print(res)


def main():
	(n, d) = map(int, input().split())
	x = list(map(int, input().split()))
	ans = j = 0
	for i in range(2, n):
		while x[i] - x[j] > d:
			j += 1
		span = i - j
		ans += span * (span - 1) // 2
	print(ans)
main()


def nc3(cnt):
	if n < 2:
		return 0
	return n * (n - 1) // 2
(n, d) = map(int, input().split())
l = [int(i) for i in input().split()]
from collections import Counter
from bisect import bisect_right as br
c = Counter(l)
ans = 0
for i in range(n):
	cnt = 0
	ind = br(l, l[i] + d)
	cnt = ind - i - 1
	ans += max(0, cnt * (cnt - 1) // 2)
print(ans)


from bisect import bisect_left

def main():
	(n, d) = map(int, input().split())
	a = [int(i) for i in input().split()]
	ans = 0
	for r in range(n - 1, -1, -1):
		l = bisect_left(a, a[r] - d)
		k = r - l + 1 - 1
		ans += k * (k - 1) // 2
	print(ans)
main()


from collections import deque
(n, d) = [int(i) for i in input().split()]
Deq = [int(j) for j in input().split()]
cnt = 0
ind = 1
j = 1
for i in range(0, n - 2):
	while j < n - 1:
		if Deq[j + 1] - Deq[i] <= d:
			j += 1
		else:
			break
	l = j - i
	if l == 0 & i < n - 3:
		j += 1
		continue
	if j == n - 1:
		cnt += (l + 1) * l * (l - 1) // 6
		break
	else:
		cnt += l * (l - 1) // 2
print(cnt)


def binarysearch(n, seq):
	low = 0
	high = len(seq) - 1
	while low < high:
		mid = (high + low + 1) // 2
		if seq[mid] > n:
			high = mid - 1
		else:
			low = mid
	return low
(n, d) = map(int, input().split())
seq = [int(x) for x in input().split()]
ans = 0
for (idx, i) in enumerate(seq):
	idx2 = binarysearch(i + d, seq)
	num_in_bw = idx2 - idx
	ans += num_in_bw * (num_in_bw - 1) // 2
print(ans)


import sys
input = sys.stdin.readline
(a, b) = map(int, input().split())
z = list(map(int, input().split()))
l = 0
r = 1
count = 0
ans = []
tot = 0
if len(z) < 3:
	print(0)
	exit()
while l <= r:
	if z[r] - z[l] <= b:
		count += 1
		r += 1
	else:
		ans.append(count)
		count = count - 1
		l += 1
	if r == len(z):
		r = len(z) - 1
		while l <= r:
			if r - l >= 2:
				ans.append(r - l)
			l += 1
		break
for i in range(len(ans)):
	if ans[i] >= 2:
		tot += ans[i] * (ans[i] - 1) // 2
print(tot)


import os
import sys
import math
from io import BytesIO, IOBase
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def dijkstra(start, distance, path, n):
	visited = [False for _ in range(n)]
	distance[start] = 0
	for i in range(n):
		v = -1
		for j in range(n):
			if not visited[v] and (v == -1 or distance[j] < distance[v]):
				v = j
		if distance[v] == math.inf:
			break
		visited[v] = True
		for edge in adj[v]:
			destination = edge[0]
			weight = edge[1]
			if distance[v] + weight < distance[destination]:
				distance[destination] = distance[v] + weight
				path[destination] = v

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def ncr(n, r):
	return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def npr(n, r):
	return math.factorial(n) // math.factorial(n - r)

def seive(n):
	primes = [True] * (n + 1)
	ans = []
	for i in range(2, n):
		if not primes[i]:
			continue
		j = 2 * i
		while j <= n:
			primes[j] = False
			j += i
	for p in range(2, n + 1):
		if primes[p]:
			ans += [p]
	return ans

def factors(n):
	factors = []
	x = 1
	while x * x <= n:
		if n % x == 0:
			if n // x == x:
				factors.append(x)
			else:
				factors.append(x)
				factors.append(n // x)
		x += 1
	return factors

def main():
	try:
		(n, d) = invr()
		a = inlt()
		ans = 0
		(i, j) = (0, 2)
		while j < n and a[j] - a[i] <= d:
			ans += (j - i - 1) * (j - i) // 2
			j += 1
		while i < n:
			i += 1
			while j < n and a[j] - a[i] <= d:
				ans += (j - i - 1) * (j - i) // 2
				j += 1
		print(ans)
	except Exception as e:
		print(e)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
mod2 = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def IF(c, t, f):
	return t if c else f

def YES(c):
	return IF(c, 'YES', 'NO')

def Yes(c):
	return IF(c, 'Yes', 'No')

def main():
	t = 1
	rr = []
	for _ in range(t):
		(n, d) = LI()
		a = LI()
		a.append(inf)
		r = 0
		j = 0
		for i in range(n):
			while a[j + 1] <= a[i] + d:
				j += 1
			r += (j - i) * (j - i - 1) // 2
		rr.append(r)
	return JA(rr, '\n')
print(main())


import math
from sys import stdin

def binary_search(data, val):
	test = len(data)
	if val >= data[-1]:
		return [test - 1, test - 1]
	elif val <= data[0]:
		return [0, 0]
	high_index = len(data) - 1
	low_index = 0
	while high_index > low_index:
		index = (high_index + low_index) // 2
		sub = data[index]
		if data[low_index] == val:
			return [low_index, low_index]
		elif sub == val:
			return [index, index]
		elif data[high_index] == val:
			return [high_index, high_index]
		elif sub > val:
			if high_index == index:
				return sorted([high_index, low_index])
			high_index = index
		else:
			if low_index == index:
				return sorted([high_index, low_index])
			low_index = index
	return sorted([high_index, low_index])
(n, m) = map(int, input().split(' '))
l = list(map(int, stdin.readline().rstrip().split(' ')))
ans = 0
for i in range(n):
	x = binary_search(l, l[i] + m)
	c = x[0] - i
	if c > 1:
		ans += c * (c - 1) // 2
print(ans)


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)


(n, d) = map(int, input().split())
ar = list(map(int, input().split()))
ans = 0
ind1 = 0
ind2 = 0
while ind1 < n:
	while ind2 < n and ar[ind1] - ar[ind2] > d:
		ind2 += 1
	t = ind1 - ind2
	ans = ans + t * (t - 1) // 2
	ind1 += 1
print(ans)


(n, k) = list(map(int, input().split()))
lis = list(map(int, input().split()))

def find(s, lis, a, k):
	l = s
	r = len(lis) - 1
	while r - l > 1:
		mid = (l + r) // 2
		if lis[mid] < a + k:
			l = mid
		else:
			r = mid
	if lis[r] <= a + k:
		return r
	return l
nat = 0

def entekhab(y):
	return int(y * (y - 1) / 2)
s = 0
for i in range(n):
	now = lis[i]
	loc = find(i, lis, now, k)
	if now + k >= lis[loc]:
		nat += entekhab(loc - i)
print(int(nat))


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

def lower_bound(value):
	(first, last) = (0, len(a))
	while first < last:
		mid = (first + last) // 2
		if value <= a[mid]:
			last = mid
		else:
			first = mid + 1
	return first
for i in range(n):
	j = lower_bound(a[i] - d)
	l = i - j
	if l >= 2:
		ans += l * (l - 1) // 2
print(ans)


def fact(x, y):
	ans = 1
	for i in range(x - y + 1, x + 1):
		ans *= i
	return ans
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.append(10 ** 12 + 1)
(i, j, t) = (0, 2, [])
while j < n + 1:
	if a[j] - a[i] > k:
		if j - i >= 3 and a[j - 1] - a[i] <= k:
			t.append((i, j))
		i += 1
	if a[j] - a[i] <= k or j - i < 2:
		j += 1
ans = 0
for (a, b) in t:
	ans += fact(b - a, 3) // fact(3, 3)
for i in range(1, len(t)):
	(start, end) = (t[i][0], t[i - 1][1])
	if end - start >= 3:
		ans -= fact(end - start, 3) // fact(3, 3)
print(ans)


R = lambda : map(int, input().split())
(n, k) = R()
cs = list(R())
(r, res) = (0, 0)
for l in range(n):
	while r < n and cs[r] - cs[l] <= k:
		r += 1
	res += (r - l - 1) * (r - l - 2) // 2 if r - l > 2 else 0
print(res)


(n, d) = map(int, input().split())
x = [int(i) for i in input().split()]
amounts = [1]
for num in range(2, 10 ** 5):
	amounts.append(amounts[-1] + num)
num_of_options = 0
ind = 0
ind2 = 0
while ind2 < n:
	if abs(x[ind] - x[ind2]) <= d:
		if ind2 - ind >= 2:
			num_of_options += amounts[ind2 - ind - 2]
		ind2 += 1
	else:
		while abs(x[ind] - x[ind2]) > d:
			ind += 1
print(num_of_options)


def f(a, j, d):
	l = j
	r = len(a)
	while r - l > 1:
		m = (r + l) // 2
		if a[m] > d:
			r = m
		elif a[m] < d:
			l = m
		else:
			return m + 1 - j - 1
	return r - j - 1
(n, d) = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
	x = f(a, i, a[i] + d)
	ans += x * (x - 1) // 2
print(ans)