Given a sequence of integers $a$, a triplet $(a[i],a[j],a[k])$ is beautiful if:

$i\lt j\lt k$
$a[j]-a[i]=a[k]-a[j]=d$

Given an increasing sequenc of integers and the value of $\boldsymbol{d}$, count the number of beautiful triplets in the sequence.

Example 

$arr=[2,2,3,4,5]$ 

$\boldsymbol{d}=1$    

There are three beautiful triplets, by index: $[i,j,k]=[0,2,3],[1,2,3],[2,3,4]$.  To test the first triplet, $ar r[j]-ar r[i]=3-2=1$ and $ar r[k]-ar r[j]=4-3=1$.  

Function Description  

Complete the beautifulTriplets function in the editor below.     

beautifulTriplets has the following parameters:  

int d: the value to match   
int arr[n]:  the sequence, sorted ascending   

Returns   

int: the number of beautiful triplets   

Input Format

The first line contains $2$ space-separated integers, $n$ and $\boldsymbol{d}$, the length of the sequence and the beautiful difference. 

The second line contains $n$ space-separated integers $arr\left[i\right]$.

Constraints

$1\leq n\leq10^4$
$1\leq d\leq20$
$0\leq\textit{arr}[i]\leq2\times10^4$
$ar r[i]>ar r[i-1]$

Sample Input
STDIN           Function
-----           --------
7 3             arr[] size n = 7, d = 3
1 2 4 5 7 8 10  arr = [1, 2, 4, 5, 7, 8, 10]

Sample Output
3

Explanation

There are many possible triplets $(arr[i],ar r[j],ar r[k])$, but our only beautiful triplets are $(1,4,7)$ , $(4,7,10)$ and $(2,5,8)$ by value, not index. Please see the equations below:    

$7-4=4-1=3=d$ 

$10-7=7-4=3=d$ 

$8-5=5-2=3=d$  

Recall that a beautiful triplet satisfies the following equivalence relation: $arr[j]-arr[i]=arr[k]-arr[j]=d$ where $i\lt j\lt k$.

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
(n, d) = map(int, input().split())
a = list(map(int, input().split()))
cnt = {}
left = []
for x in a:
	left.append(cnt.get(x - d, 0))
	if x not in cnt:
		cnt[x] = 0
	cnt[x] += 1
left = left[::-1]
cnt = {}
res = 0
for (i, x) in enumerate(a[::-1]):
	res += left[i] * cnt.get(x + d, 0)
	cnt[x] = cnt.get(x, 0) + 1
print(res)


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


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
s = set(a)
ans = 0
for i in a:
	if i + d in s and i + 2 * d in s:
		ans += 1
print(ans)


(n, d) = [int(temp) for temp in input().strip().split()]
a = [int(temp) for temp in input().strip().split()]
total = 0
for i in range(n - 2):
	if a[i] + d in a and a[i] + d * 2 in a:
		total += 1
print(total)


import sys
(l, d) = [int(c_temp) for c_temp in input().strip().split(' ')]
sequence = [int(c_temp) for c_temp in input().strip().split(' ')]
result = 0
for i in sequence:
	if i - d in sequence and i + d in sequence:
		result += 1
print(result)


(n, d) = [int(i) for i in input().strip().split()]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
cnt = 0
for i in range(n):
	two = c[i] + d
	three = two + d
	if two in c[i + 1:] and three in c[i + 2:]:
		cnt += 1
print(cnt)


(n, d) = (int(_) for _ in input().split())
a = [int(_) for _ in input().split()]
s = set(a)
ans = 0
for i in a:
	if i - d in s and i + d in s:
		ans += 1
print(ans)


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
b = [i + d for i in a]
c = [i + d for i in b]
x = set(a) & set(b) & set(c)
print(len(x))


from sys import stderr
(n, d) = [int(x) for x in input().strip().split(' ')]
a = [int(x) for x in input().strip().split(' ')]
c = 0
for i in range(n):
	x = a[i] + d
	done = False
	for j in range(i, n):
		if a[j] >= x:
			break
	else:
		done = True
	if a[j] == x:
		x += d
		for k in range(j, n):
			if a[k] >= x:
				break
		else:
			done = True
		if a[k] == x:
			c += 1
	if done:
		break
print(c)


def beau(nums, d):
	count = 0
	for num in nums:
		if num + d in nums and num + 2 * d in nums:
			count += 1
	return count
(n, d) = tuple((int(i) for i in input().strip().split(' ')))
nums = [int(i) for i in input().strip().split(' ')]
print(beau(nums, d))


(n, d) = [int(r) for r in input().split()]
a = [int(r) for r in input().split()]
triplets = 0
for i in range(n - 2):
	for j in range(i + 1, n - 1):
		if a[j] - a[i] == d:
			foundTrip = False
			for k in range(j + 1, n):
				if a[k] - a[j] == d:
					triplets += 1
					foundTrip = True
					break
			if foundTrip == True:
				break
print(triplets)


(n, d) = list(map(int, input().strip().split()))
a = list(map(int, input().strip().split()))
sol = 0
indices = list(range(n))
while len(indices) > 0:
	i = indices[0]
	count = 1
	ini = a[i]
	temp_indices = indices[1:]
	for j in temp_indices:
		if ini + d == a[j]:
			indices.remove(j)
			ini = a[j]
			count += 1
		elif ini + d < a[j]:
			break
	if count > 2:
		sol += count - 2
	indices.remove(i)
print(sol)


(n, d) = list(map(int, input().split()))
a = list(map(int, input().split()))
ans = 0
for i in range(len(a) - 1):
	flag = 0
	for j in range(i + 1, len(a)):
		if a[j] - a[i] == d:
			flag = 1
			for k in range(j + 1, len(a)):
				if a[k] - a[j] == d:
					ans += 1
					break
		if flag == 1:
			break
print(ans)


(n, d) = input().split()
n = int(n)
d = int(d)
a = list(map(int, input().split()))
count = 0
i = 0
while a[i] + d <= a[n - 1]:
	val = a[i] + d
	if val in a:
		val1 = val + d
		if val1 in a:
			count = count + 1
	i = i + 1
print(count)


(n, d) = map(lambda x: int(x), input().split())
a = list(map(lambda x: int(x), input().split()))
data = [0] * 100000
for el in a:
	data[el] = 1
ans = 0
for i in range(n):
	if data[a[i]] == 1 and data[a[i] + d] == 1 and (data[a[i] + 2 * d] == 1):
		ans += 1
print(ans)


(n, d) = list(map(int, input().split()))
a = list(map(int, input().split()))
diff = [0 for i in range(n)]
for i in range(n - 1):
	diff[i] = a[i + 1] - a[i]
count = 0
for y in range(0, n - 1):
	p = y
	q = y + 1
	sum1 = 0
	sum2 = 0
	flag1 = 0
	flag2 = 0
	while sum1 < d and p > -1:
		sum1 += diff[p]
		p -= 1
	if sum1 == d:
		flag1 = 1
	while sum2 < d and q < n:
		sum2 += diff[q]
		q += 1
	if sum2 == d:
		flag2 = 1
	if flag1 == 1 and flag2 == 1:
		count += 1
print(count)


import sys
list1 = [int(c) for c in sys.stdin.readline().split()]
sequences = [int(n) for n in sys.stdin.readline().split()]
length = list1[0]
diff = list1[1]
found = 0
for i in range(length - 2):
	for j in range(i + 1, length - 1):
		if sequences[j] - sequences[i] != diff:
			continue
		for k in range(j + 1, length):
			if sequences[k] - sequences[j] > diff:
				break
			elif sequences[k] - sequences[j] == diff:
				found += 1
print(found)


import sys
(n, d) = input().strip().split(' ')
(n, d) = [int(n), int(d)]
a = [int(c) for c in input().strip().split(' ')]
cnt = 0
for i in range(n):
	try:
		a1 = a.index(a[i] + d)
		a2 = a.index(a[i] + d + d)
	except:
		a1 = -1
		a2 = -1
		pass
	if a1 != -1 and a2 != -1:
		cnt += 1
print(cnt)


def is_good_pair(a, b, d):
	return b - a == d

def n_beautiful(l, d):
	count = 0
	n = len(l)
	for i in range(n - 2):
		skip = False
		j = i + 1
		while not skip:
			if j == n - 2:
				skip = True
			if l[j] - l[i] > d:
				skip = True
			if is_good_pair(l[i], l[j], d):
				skip2 = False
				k = j + 1
				while not skip2:
					if k == n - 1:
						skip2 = True
					if l[k] - l[j] > d:
						skip2 = True
					if is_good_pair(l[j], l[k], d):
						count += 1
					k += 1
			j += 1
	return count

def test():
	l = [1, 2, 4, 5, 7, 8, 10]
	assert n_beautiful(l, 3) == 3

def hackerrank():
	digs = [int(i) for i in input().split()]
	l = [int(i) for i in input().split()]
	print(n_beautiful(l, digs[1]))
hackerrank()


(n, d) = map(int, input().split())
arr = list(map(int, input().split()))
ans = 0
for i in range(n - 2):
	k = d + arr[i]
	if k in arr[i:n - 1]:
		kk = d + k
		where = arr.index(k)
		if kk in arr[where + 1:]:
			ans += 1
print(ans)


(n, d) = [int(x) for x in input().split()]
a = set([int(x) for x in input().split()])
s = 0
for ia in a:
	if ia + d in a and ia + d + d in a:
		s += 1
print(s)


(n, d) = [int(i) for i in input().strip().split()]
arr = [int(i) for i in input().strip().split()]
count = 0
if n >= 3:
	for i in range(n - 2):
		for j in range(i + 1, n - 1):
			if arr[j] - arr[i] != d:
				continue
			elif arr[j] - arr[i] > d:
				break
			else:
				for k in range(j + 1, n):
					if arr[k] - arr[j] > d:
						break
					elif arr[k] - arr[j] == d:
						count += 1
print(count)


(n, d) = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
s = set(l)
m = max(l)
cnt = 0
for n in s:
	if n + 2 * d > m:
		break
	x = n + d
	y = x + d
	if x in s and y in s:
		cnt += 1
print(cnt)


(n, d) = list(map(int, input().rstrip().split()))
a = list(map(int, input().rstrip().split()))
c = 0
for i in range(n):
	if a[i] + d in a and a.index(a[i] + d) > i:
		if a[i] + 2 * d in a and a.index(a[i] + 2 * d) > a.index(a[i] + d):
			c += 1
print(c)


(n, d) = [int(c_temp) for c_temp in input().strip().split(' ')]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
i = n - 1
count = 0
while i > 1:
	temp = c[i]
	if temp - d in c:
		if temp - d - d in c:
			count += 1
	i -= 1
print(count)


import sys
(n, d) = [int(x) for x in input().strip().split(' ')]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
if len(c) < 3:
	print(0)
	sys.exit(0)
protos = []
num = 0
for i in range(n - 2):
	b1 = i
	b2 = b1
	while c[b2] < c[b1] + d and b2 + 1 < n - 1:
		b2 += 1
	if c[b2] != c[b1] + d:
		continue
	b3 = b2
	while c[b3] < c[b2] + d and b3 + 1 < n:
		b3 += 1
	if c[b3] == c[b2] + d:
		num += 1
print(num)


(n, d) = [int(t) for t in input().strip().split(' ')]
a = [int(t) for t in input().strip().split(' ')]

def bsearch(a, start, end, num):
	curr = (start + end) // 2
	if start > end:
		return -1
	if a[curr] == num:
		return curr
	elif a[curr] > num:
		return bsearch(a, start, curr - 1, num)
	else:
		return bsearch(a, curr + 1, end, num)
numTriplets = 0
for i in range(n - 2):
	j = bsearch(a, i, n - 1, a[i] + d)
	if j != -1 and j != n - 1:
		k = bsearch(a, j, n - 1, a[j] + d)
		if k != -1:
			numTriplets += 1
print(numTriplets)


(n, d) = map(int, input().split())
s = list(map(int, input().split()))
cnt = 0
for i in range(n):
	(l, m) = (i - 1, i + 1)
	while l >= 0 and s[i] - s[l] < d:
		l -= 1
	while m <= n - 1 and s[m] - s[i] < d:
		m += 1
	if l >= 0 and m <= n - 1 and (d == s[i] - s[l] == s[m] - s[i]):
		cnt += 1
print(cnt)


(n, d) = [int(i) for i in input().split()]
nums = [int(i) for i in input().split()]
count = 0
for x in range(len(nums) - 2):
	if nums[x] + d in nums:
		if nums[x] + d + d in nums:
			count += 1
print(count)


(n, d) = map(int, input().strip().split())
a = [int(x) for x in input().strip().split()]
cnt = 0
for j in range(1, n - 1):
	i = j - 1
	while i > -1 and a[i] + d >= a[j]:
		if a[i] + d == a[j]:
			k = j + 1
			while k < n and a[k] <= a[j] + d:
				if a[j] + d == a[k]:
					cnt += 1
					break
				k += 1
			break
		i -= 1
print(cnt)


import sys
(n, d) = (int(c_temp) for c_temp in input().strip().split(' '))
a = [int(c_temp) for c_temp in input().strip().split(' ')]
aToIndex = {}
for i in range(n):
	aToIndex[a[i]] = i
result = 0
for i in range(n):
	j = aToIndex.get(a[i] + d)
	k = aToIndex.get(a[i] + 2 * d)
	if j and k and (j > i) and (k > j):
		result += 1
print(result)


(n, d) = map(int, input().strip().split(' '))
pairs = {}
seq = [int(x) for x in input().strip().split(' ')]
for i in range(len(seq)):
	for j in range(i + 1, len(seq)):
		if seq[j] - seq[i] == d:
			if not i in pairs:
				pairs[i] = []
			pairs[i].append(j)
pair_count = 0
for i in pairs.keys():
	for j in pairs[i]:
		pair_count += len(pairs.get(j, []))
print(pair_count)


import sys
(n, d) = [int(i) for i in input().strip().split(' ')]
a = [int(v) for v in input().strip().split(' ')]
i = 0
c = 0
while i + 2 < n:
	j = i + 1
	while j + 1 < n and a[j] - a[i] < d:
		j = j + 1
	if j < n and a[j] - a[i] == d:
		k = j + 1
		while k < n and a[k] - a[j] < d:
			k = k + 1
		if k < n and a[k] - a[j] == d:
			c = c + 1
	i = i + 1
print(c)


(seq_len, d) = input().split()
d = int(d)
a = [int(x) for x in input().split()]
triplets = 0
size = len(a)
idx_i = 0
idx_j = 1
while idx_i < size - 1:
	i = a[idx_i]
	try:
		idx_j = a.index(i + d)
		j = a[idx_j]
		try:
			idx_k = a.index(j + d)
			triplets += 1
		except:
			pass
	except:
		pass
	idx_i += 1
print(triplets)


first_line = input().strip().split()
n = int(first_line[0])
d = int(first_line[1])
sequence = [int(x) for x in input().strip().split()]
triplets = 0
for i in range(len(sequence) - 2):
	num = sequence[i]
	if num + d in sequence and num + 2 * d in sequence:
		triplets += 1
print(triplets)


first_line = [int(entry) for entry in input().strip().split(' ')]
numbers = [int(entry) for entry in input().strip().split(' ')]
length = first_line[0]
d = first_line[1]
sum_of_beautiful_triplets = 0
for i in range(0, length):
	for j in range(i + 1, length):
		if numbers[j] - numbers[i] > d:
			break
		if numbers[j] - numbers[i] == d:
			for k in range(j + 1, length):
				if numbers[k] - numbers[j] > d:
					break
				if numbers[k] - numbers[j] == d:
					sum_of_beautiful_triplets += 1
print(sum_of_beautiful_triplets)


(n, d) = map(int, input().split())
s = list(map(int, input().split()))
cou = 0
for i in range(n - 2):
	a = s[i]
	for j in range(i + 1, n - 1):
		if s[j] == a + d:
			b = s[j]
			for k in range(j + 1, n):
				if s[k] == b + d:
					cou += 1
				if s[k] > b + d:
					break
		if s[j] > a + d:
			break
print(cou)


from collections import defaultdict
(n, d) = map(int, input().strip().split())
a = [int(x) for x in input().strip().split()]
diffs = defaultdict(set)
for i in range(len(a)):
	for j in range(i + 1, len(a)):
		diff = a[j] - a[i]
		if diff == d:
			diffs[i].add(j)
		if diff > d:
			break
acc = 0
for (start, ends) in diffs.items():
	for end in ends:
		acc += end in diffs
print(acc)


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
pairs = 0
a = 0
b = 1
c = 2
while c < n and a < n and (b < n):
	if l[b] - l[a] == k:
		if l[c] - l[b] == k:
			pairs += 1
			a += 1
			b += 1
			c += 1
		elif l[c] - l[b] < k:
			c += 1
		else:
			a += 1
			b += 1
	elif l[b] - l[a] < k:
		b += 1
	else:
		a += 1
	if c <= b:
		c += 1
print(pairs)


import sys
int
line = [int(c_temp) for c_temp in input().strip().split(' ')]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
d = line[1]
n = line[0]
flag = 0
triplet = 0
for i in range(n - 2):
	flag = 0
	ne = c[i]
	for j in range(2):
		flag = 0
		ne = ne + d
		if ne not in c:
			flag = -999
			break
		else:
			continue
	if flag == 0:
		triplet = triplet + 1
		flag = 0
print(triplet)


(n, d) = map(int, input().split())
nums = [int(i) for i in input().strip().split(' ')]
i = count = 0
max_n = nums[-1]
while i < n - 2:
	n1 = nums[i] + d
	n2 = n1 + d
	if n1 in nums and n2 in nums:
		count += 1
		if n2 == max_n:
			break
	i += 1
print(count)


(N, D) = map(int, input().split())
a = list(map(int, input().split()))
count = 0
for (i, ai) in enumerate(a[:-2]):
	for (j, aj) in enumerate(a[i + 1:-1]):
		j = i + 1 + j
		d1 = aj - ai
		if d1 == D:
			ak = D + aj
			if ak in a[j + 1:]:
				count += 1
		elif d1 > D:
			break
print(count)


def main():
	line = input().split()
	n = int(line[0])
	d = int(line[1])
	arr = [int(i) for i in input().split()]
	diff = []
	if n == 1:
		print(0)
		return
	for i in range(n - 1):
		diff.append(arr[i + 1] - arr[i])
	subSeq = [diff[0]]
	subSeqIndx = [0, 0]
	tripletList = []
	while subSeqIndx[1] < len(diff):
		if sum(subSeq) == d:
			tripletList.append(subSeqIndx)
			try:
				subSeq = [diff[subSeqIndx[0] + 1]]
				subSeqIndx = [subSeqIndx[0] + 1, subSeqIndx[0] + 1]
			except:
				break
		else:
			while sum(subSeq) > d:
				subSeq.pop(0)
				subSeqIndx[0] += 1
			if sum(subSeq) == d:
				continue
			elif subSeqIndx[1] + 1 < len(diff):
				subSeq.append(diff[subSeqIndx[1] + 1])
				subSeqIndx[1] += 1
			else:
				break
	count = 0
	for i in range(len(tripletList)):
		for j in range(i + 1, len(tripletList)):
			if tripletList[i][1] + 1 == tripletList[j][0]:
				count += 1
	print(count)
main()


(n, d) = map(int, input().split())
a = [int(i) for i in input().split()]
(dl, dr) = ({}, {})
for i in range(len(a)):
	for j in range(i + 1, len(a)):
		if a[j] - a[i] == d:
			dl[a[j]] = dl.get(a[j], 0) + 1
			dr[a[i]] = dr.get(a[i], 0) + 1
c = 0
for i in dl:
	if i in dr:
		c += dl[i] * dr[i]
print(c)


from sys import stdin
(n, d) = map(int, stdin.readline().split())
arr = list(map(int, stdin.readline().split()))
m = {}
for i in range(n):
	m[arr[i]] = i
count = 0
for i in range(n - 1):
	v = arr[i]
	if v + d in m and v + 2 * d in m:
		(j, k) = (m[v + d], m[v + 2 * d])
		if i < j and j < k:
			count += 1
print(count)


(n, d) = input().strip().split(' ')
n = int(n)
d = int(d)
A = [int(c_temp) for c_temp in input().strip().split(' ')]
nbrSeq = 0
if n > 2:
	firstValuePointer = -1
	while True:
		flag = 0
		firstValuePointer += 1
		if firstValuePointer > n - 1:
			break
		firstValue = A[firstValuePointer]
		secondValuePointer = firstValuePointer
		while True:
			secondValuePointer += 1
			if secondValuePointer > n - 1:
				break
			secondValue = A[secondValuePointer]
			currentDiff = secondValue - firstValue
			if currentDiff == d:
				thirdValuePointer = secondValuePointer
				while True:
					thirdValuePointer += 1
					if thirdValuePointer > n - 1:
						break
					thirdValue = A[thirdValuePointer]
					currentDiff2 = thirdValue - secondValue
					if currentDiff2 == d:
						nbrSeq += 1
						flag = 1
						break
					elif currentDiff2 > d:
						break
			elif currentDiff > d:
				break
			if flag:
				break
print(nbrSeq)


import sys
(n, d) = [int(inp) for inp in input().strip().split(' ')]
a = [int(c_temp) for c_temp in input().strip().split(' ')]
len_a = len(a)
count = 0
for i in range(0, len_a - 2):
	a_i = a[i]
	for j in range(i + 1, len_a - 1):
		a_j = a[j]
		a_j_i = a_j - a_i
		if a_j_i > d:
			break
		if a_j_i == d:
			for k in range(j + 1, len_a):
				a_k = a[k]
				a_k_j = a_k - a_j
				if a_k_j > d:
					break
				if a_k_j == d:
					count += 1
					break
print(count)


d = input()
d = int(d.split()[1])
a = input()
a = a.split()
a = [int(i) for i in a]
numel = 0
for i in range(len(a)):
	curr = a[i]
	test = curr + d
	if test in a and a.index(test) > i:
		curr = a[a.index(test)]
		test = curr + d
		if test in a and a.index(test) > i:
			numel = numel + 1
print(numel)


line = input()
n = int(line.strip().split(' ')[0])
d = int(line.strip().split(' ')[1])
line = input()
c = [int(c_i) for c_i in line.strip().split(' ')]
count = 0
for i in range(0, n - 2):
	found = 0
	for j in range(i + 1, n - 1):
		if c[j] - c[i] > 20:
			break
		elif c[j] - c[i] == d:
			cur2 = c[j]
			for k in range(j + 1, n):
				if c[k] - c[j] > 20:
					found = 1
					break
				elif c[k] - c[j] == d:
					count += 1
					found = 1
					break
		if found:
			break
print(count)


def get_number_of_beautiful_triplets(numbers, beautiful_diff):
	indexed_numbers = {k: v for (k, v) in zip(numbers, range(0, len(numbers)))}
	number_of_beautiful_triplets = 0
	for number in numbers:
		number_plus_bd = number + beautiful_diff
		if number_plus_bd in indexed_numbers:
			number_plus_2bd = number_plus_bd + beautiful_diff
			if number_plus_2bd in indexed_numbers:
				number_of_beautiful_triplets += 1
	return number_of_beautiful_triplets
(number_of_numbers, beautiful_difference) = [int(i) for i in input().split()]
numbers = [int(i) for i in input().strip().split()]
print(get_number_of_beautiful_triplets(numbers, beautiful_difference))


(n, d) = [int(i) for i in input().strip().split(' ')]
seq = set([int(i) for i in input().strip().split(' ')])
ans = 0
for i in seq:
	x = i + d
	if x in seq and x + d in seq:
		ans += 1
print(ans)


(n, d) = list(map(int, input().split()))
a = list(map(int, input().split()))
count = 0
for i in range(n):
	if a[i] + d in a[i + 1:]:
		if a[i] + 2 * d in a[a.index(a[i] + d) + 1:]:
			count += 1
print(count)


(n, d) = input().split()
(n, d) = (int(n), int(d))
vals = [int(i) for i in input().split()]
triplets = 0
maximum = max(vals)
existsDict = {}
for num in vals:
	existsDict[num] = True
for num in vals:
	(first, second, third) = (num, num + d, num + d + d)
	try:
		(a, b, c) = (existsDict[first], existsDict[second], existsDict[third])
		triplets = triplets + 1
	except KeyError:
		continue
print(triplets)


line1 = [int(c_temp) for c_temp in input().strip().split(' ')]
l = line1[0]
d = line1[1]
v = [int(c_temp) for c_temp in input().strip().split(' ')]
i = 0
j = 1
k = 2
perfect_diference = 0
if l > 2:
	if v[j] - v[i] is d and v[k] - v[j] is d:
		perfect_diference = perfect_diference + 1
	k = k + 1
	while k < l:
		while j < k:
			while i < j and v[k] - v[j] <= 20:
				if v[j] - v[i] is d and v[k] - v[j] is d:
					perfect_diference = perfect_diference + 1
				i = i + 1
			i = 0
			j = j + 1
			if j - 20 > 0:
				i = j - 20
		k = k + 1
		i = 0
		if j - 20 > 0:
			i = j - 20
		j = 1
		if k - 20 > 0:
			j = k - 20
print(perfect_diference)


(n, d) = [int(x) for x in input().split()]
lst = [int(x) for x in input().split()]
mp = dict(((x, i) for (i, x) in enumerate(lst)))
res = [e for e in mp.keys() if e + d in mp and e + d + d in mp]
print(len(res))


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
count = 0
for i in range(len(a) - 2):
	if a[i] + d in a and a[i] + d + d in a:
		count += 1
print(count)


(n, d) = map(int, input().split())
array = list(map(int, input().split()))
count = 0
visited = [False] * n
i = 0
while i < n:
	if visited[i]:
		i += 1
	else:
		visited[i] = True
		count_3 = 1
		start = array[i]
		j = i + 1
		while j < n:
			if start + d == array[j]:
				count_3 += 1
				start = array[j]
				visited[j] = True
			j += 1
		if count_3 >= 3:
			count += count_3 - 2
		i += 1
print(count)


def all_beautiful_triplets(numbers, difference):
	return sum((all((numbers[i] + difference * j in numbers for j in (1, 2))) for i in range(len(numbers) - difference)))

def main():
	(_, difference) = input().split()
	difference = int(difference)
	sequence = [int(x) for x in input().strip().split()]
	print(all_beautiful_triplets(sequence, difference))
main()


import sys
(n, d) = [int(x) for x in input().strip().split(' ')]
a = [int(x) for x in input().strip().split(' ')]

def FindBeautifulForIndex(i):
	for j in range(i + 1, n):
		dist = a[j] - a[i]
		if dist == d:
			return j
		if dist > d:
			break
	return -1
count = 0
for i in range(0, n - 1):
	j = FindBeautifulForIndex(i)
	if (j == -1) | (j >= n - 1):
		continue
	k = FindBeautifulForIndex(j)
	if k != -1:
		count = count + 1
print(count)


(n, d) = [int(x) for x in input().strip().split()]
a_list = [int(x) for x in input().strip().split()]
length = len(a_list)
counter = 0
found = False
for i in range(length):
	for j in range(i, 0, -1):
		if a_list[i] - a_list[j] == d:
			for k in range(j, -1, -1):
				if a_list[j] - a_list[k] == d:
					counter += 1
					found = True
					break
		if found:
			found = False
			break
print(counter)


(n, d) = input().split()
n = int(n)
d = int(d)
count = 0
a = [int(c_temp) for c_temp in input().strip().split(' ')]
for i in range(n):
	j = a[i] + d
	if j in a:
		k = j + d
		if k in a:
			count = count + 1
print(count)


(n, d) = input().strip().split(' ')
(n, d) = [int(n), int(d)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
count = 0
for i in range(len(c) - 1, -1, -1):
	temp = 0
	for j in range(i - 1, -1, -1):
		if c[i] - c[j] == d:
			i = j
			temp += 1
			if temp == 2:
				count += 1
				break
print(count)


(n, d) = list(map(int, input().split()))
arr = list(map(int, input().split()))
ans = 0
for i in range(0, n - 2):
	current = arr[i]
	aux = arr[i] + d
	if aux in arr:
		ind = arr.index(aux)
		aux = arr[ind] + d
		if aux in arr:
			ans += 1
print(ans)


(n, d) = list(map(int, input().strip().split(' ')))
a = list(map(int, input().strip().split(' ')))
ans = 0
for i in range(0, n - 2):
	for j in range(i + 1, n - 1):
		if a[j] - a[i] > d:
			break
		if a[j] - a[i] < d:
			continue
		for k in range(j + 1, n):
			if a[k] - a[j] > d:
				break
			if a[k] - a[j] < d:
				continue
			ans += 1
			break
print(ans)


(n, d) = map(int, input().strip().split())
A = [int(a) for a in input().strip().split()]
second = list()
count = 0
for a in A:
	if a + d in A:
		if a in second:
			count += 1
		second.append(a + d)
print(count)


def get_triplets(n, d, a):
	count = 0
	triplets = []
	while count < n:
		pivot = a[count]
		triplet = [pivot]
		for i in range(count + 1, n):
			if a[i] - pivot == d:
				triplet.append(a[i])
				pivot = a[i]
		triplet = triplet if len(triplet) == 3 else triplet[:3]
		diff = [j - i for (i, j) in zip(triplet[:-1], triplet[1:])]
		if set(diff) == set([d]) and len(triplet) == 3:
			triplets.append(tuple(triplet))
		count += 1
	print(len(triplets))
(n, d) = input().strip().split(' ')
(n, d) = [int(n), int(d)]
a = [int(a_temp) for a_temp in input().strip().split(' ')]
if n < 0 or n > 10000:
	print(0)
elif d > 20 or d < 1:
	print(0)
else:
	get_triplets(n, d, a)


(n, d) = map(int, input().strip().split())
A = [int(c_temp) for c_temp in input().strip().split(' ')]

def solve(n, d, A):
	if n < 3:
		return 0
	res = 0
	(i, j, k) = (0, 1, 2)
	while i < n - 2:
		while j + 2 < n and A[j] - A[i] < d:
			j += 1
		if j >= k:
			k = j + 1
		while k + 1 < n and A[k] - A[j] < d:
			k += 1
		if A[j] - A[i] == A[k] - A[j] == d:
			res += 1
		i += 1
	return res
print(solve(n, d, A))


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
count = 0
for i in range(0, n):
	for j in range(i + 1, n):
		if a[j] - a[i] == d:
			for k in range(j + 1, n):
				if a[k] - a[j] == d:
					count += 1
		elif a[j] - a[i] < d:
			continue
		else:
			break
print(count)


(n, d) = [int(i) for i in input().strip().split()]
a = [int(i) for i in input().strip().split()]
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		if a[j] - a[i] > d:
			break
		elif a[j] - a[i] != d:
			continue
		else:
			ans = ans + a[j + 1:].count(a[j] + d)
print(ans)


from collections import defaultdict
(n, d) = [int(i) for i in input().strip().split()]
arr = [int(i) for i in input().strip().split()]
num_to_index = defaultdict(list)
for (i, num) in enumerate(arr):
	num_to_index[num].append(i)
results = []
d2 = d + d
for num in sorted(num_to_index):
	(a, b, c) = (num, num + d, num + d2)
	if b in num_to_index and c in num_to_index:
		mx = max(num_to_index[c])
		mn = min(num_to_index[a])
		if mx > mn and any((mx > i > mn for i in num_to_index[b])):
			results.append((a, b, c))
print(len(results))


(n, d) = [int(x) for x in input().strip().split(' ')]
a = [int(x) for x in input().strip().split(' ')]
triplets = 0
known_triplets = []
for i in range(n):
	if a[i] + d in a[i:] and a[i] + 2 * d in a[i:] and ((a[i], a[i] + d, a[i] + 2 * d) not in known_triplets):
		triplets += 1
		known_triplets.append((a[i], a[i] + d, a[i] + 2 * d))
	if a[i] - d in a[:i] and a[i] + d in a[i:] and ((a[i] - d, a[i], a[i] + d) not in known_triplets):
		triplets += 1
		known_triplets.append((a[i] - d, a[i], a[i] + d))
	if a[i] - d in a[:i] and a[i] - 2 * d in a[:i] and ((a[i] - 2 * d, a[i] - d, a[i]) not in known_triplets):
		triplets += 1
		known_triplets.append((a[i] - 2 * d, a[i] - d, a[i]))
print(triplets)


input1 = input().split()
input2 = input()
seq = [int(n) for n in input2.split()]
n = int(input1[0])
d = int(input1[1])
if n >= 3:
	s = 0
	for j in range(1, n):
		for i in range(j - 1, -1, -1):
			if abs(seq[i] - seq[j]) == d:
				for k in range(j + 1, n):
					if abs(seq[j] - seq[k]) == d:
						s += 1
					elif abs(seq[j] - seq[k]) > d:
						break
				break
			elif abs(seq[i] - seq[j]) > d:
				break
	print(s)
else:
	print(0)


import sys
input_line1_list = [int(c_temp) for c_temp in input().strip().split(' ')]
elem_list = [int(c_temp) for c_temp in input().strip().split(' ')]
if len(input_line1_list) != 2:
	print('Invalid input: First line of input should be <no-of-elements> <beautiful-difference>')
	exit(1)
else:
	(no_of_elements, beautiful_diff) = input_line1_list
if no_of_elements != len(elem_list):
	print('Invalid input: <no-of-elements> does not match the actual number of elements in the List.')
	exit(1)
elem_set = frozenset(elem_list)
beautiful_triple_list = [(elem, elem - beautiful_diff, elem - 2 * beautiful_diff) for elem in elem_list if elem - beautiful_diff in elem_set and elem - 2 * beautiful_diff in elem_set]
no_of_beautiful_triples = len(beautiful_triple_list)
print(no_of_beautiful_triples)


(n, d) = input().split()
d = int(d)
c = [int(i) for i in input().split()]
count = 0
for i in c:
	a = i + d
	b = i + d + d
	if a in c and b in c:
		if c.index(i) < c.index(a) and c.index(a) < c.index(b):
			count += 1
print(count)


import math
(n, d) = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
l.sort()
l2 = {x: False for x in l}
p = []
c = 0
t = 0
for i in l:
	if l2[i] == True:
		continue
	k = i - d
	p.append([])
	for j in l:
		if j - k == d:
			p[c].append(j)
			l2[j] = True
			k = j
	q = len(p[len(p) - 1])
	if q >= 3:
		t += q - 2
	c += 1
print(t)


(n, d) = input().split()
(n, d) = (int(n), int(d))
a = [int(temp) for temp in input().split()]
ans = 0
for i in a:
	if i + d in a and i + 2 * d in a:
		ans += 1
print(ans)


nd = input().split()
n = int(nd[0])
d = int(nd[1])
a = [int(x) for x in input().split()]
counter = 0
for i in range(n):
	if a[i] + d in a:
		if a[i] + d + d in a:
			counter += 1
print(counter)


(n, d) = map(int, input().split())
l = list(map(int, input().split()))
br = 0
for i in range(0, n - 2):
	a = l[i]
	if a + d in l and a + 2 * d in l:
		br += 1
print(br)


(n, d) = list(map(int, input().split()))
a = list(map(int, input().split()))
c = 0
for i in range(n - 2):
	for j in range(i + 1, n - 1):
		if a[j] < a[i] + d:
			continue
		if a[j] > a[i] + d:
			break
		for k in range(j + 1, n):
			if a[k] < a[j] + d:
				continue
			if a[k] > a[j] + d:
				break
			c += 1
print(c)


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		if a[j] - a[i] > d:
			break
		for k in range(j + 1, n):
			if a[k] - a[j] > d:
				break
			if a[j] - a[i] == a[k] - a[j] and a[k] - a[j] == d:
				ans += 1
				break
print(ans)


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
cnt = 0
trck = [0] * 100004
lf = []
rg = []
for i in range(len(a)):
	lf.append(trck[a[i] - d])
	trck[a[i]] += 1
trck = [0] * 100004
for i in range(len(a) - 1, -1, -1):
	rg = trck[a[i] + d]
	cnt += rg * lf[i]
	trck[a[i]] += 1
print(cnt)


temp = [int(i) for i in input().split()]
count = temp[0]
d = temp[1]
numbers = [int(i) for i in input().split()]
solution = 0
for i in range(count):
	if numbers[i] + d in numbers[i:] and numbers[i] + 2 * d in numbers[i:]:
		solution += 1
print(solution)


first = input().strip().split(' ')
n = int(first[0])
d = int(first[1])
c = [int(c_temp) for c_temp in input().strip().split(' ')]
count = 0
for i in range(n):
	pivot = c[i]
	if pivot - d in c[:i] and pivot + d in c[i:]:
		count += 1
print(count)


i = input().strip().split()
n = int(i[0])
d = int(i[1])
a = [int(i) for i in input().strip().split()]

def Function(a, d):
	count = 0
	for i in range(len(a)):
		if a[i] + d in a and a[i] + 2 * d in a:
			count = count + 1
	return count
print(Function(a, d))


from itertools import combinations
(amount_num, beautiful_value) = list(map(int, input().split()))
numbers = list(map(int, input().split()))
numbers_set = set(numbers)
cursor_ai = 0
cursor_aj = 1
count_beautiful_bunches = 0
while cursor_ai < amount_num - 2:
	ai = numbers[cursor_ai]
	if ai + beautiful_value in numbers_set:
		aj = ai + beautiful_value
		if aj + beautiful_value in numbers_set:
			count_beautiful_bunches += 1
	cursor_ai += 1
print(count_beautiful_bunches)


(n, d) = [int(x) for x in input().split()]
seq = [int(x) for x in input().split()]
i = j = k = 0
triplets_count = 0
while i < n:
	if seq[i] + d in seq and seq[i] + 2 * d in seq:
		triplets_count += 1
	i += 1
print(triplets_count)


import sys
line1 = input().strip().split(' ')
n = int(line1[0])
d = int(line1[1])
c = [int(c_temp) for c_temp in input().strip().split(' ')]
inlist = [False for _ in range(20001)]
for i in c:
	inlist[i] = True
b = 0
for i in range(20001 - 2 * d):
	if inlist[i] and inlist[i + d] and inlist[i + 2 * d]:
		b += 1
print(b)


c = [int(c_temp) for c_temp in input().strip().split(' ')]
e = [int(c_temp) for c_temp in input().strip().split(' ')]
n = c[0]
d = c[1]
count = 0
for i in e:
	if i + d in e and i + 2 * d in e:
		count += 1
print(count)


import sys
(n, d) = [int(n_temp) for n_temp in input().strip().split(' ')]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
(trip1, trip2, trip3) = (set(), set(), set())
for x in c:
	if x - d in trip2:
		trip3.add(x)
	if x - d in trip1:
		trip2.add(x)
	trip1.add(x)
print(len(trip3))


import sys
param = [int(c_temp) for c_temp in input().strip().split(' ')]
seq = [int(c_temp) for c_temp in input().strip().split(' ')]
dic = {}
n = param[0]
d = param[1]
if 1 <= n and n <= 10000 and (d >= 1) and (d <= 20):
	for i in range(0, n):
		dic[seq[i]] = i
	total = 0
	for i in range(0, n - d):
		if seq[i] + d in dic and i < dic[seq[i] + d]:
			if seq[dic[seq[i] + d]] + d in dic and dic[seq[dic[seq[i] + d]] + d]:
				total += 1
	print(total)


(n, d) = map(int, input().split())
seq = list(map(int, input().split()))
middles = [-1] * d
oldest = 0
highs = [-1] * d
count = 0
for x in seq:
	if x in highs:
		count += 1
	if x in middles:
		highs[oldest] = x + d
	middles[oldest] = x + d
	oldest = (oldest + 1) % d
print(count)


(n, d) = [int(i) for i in input().strip().split()]
a = [int(i) for i in input().strip().split()]
a.sort()
count = 0
for k in a:
	if k + d in a and k + 2 * d in a:
		count += 1
print(count)


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
count = 0
for i in range(0, n):
	for j in range(i + 1, n):
		if a[j] - a[i] == d:
			for k in range(j + 1, n):
				if d == a[k] - a[j]:
					count += 1
					break
			break
print(count)