We've got no test cases. A big olympiad is coming up. But the problemsetters' number one priority should be adding another problem to the round. 

The diameter of a multiset of points on the line is the largest distance between two points from this set. For example, the diameter of the multiset {1, 3, 2, 1} is 2.

Diameter of multiset consisting of one point is 0.

You are given n points on the line. What is the minimum number of points you have to remove, so that the diameter of the multiset of the remaining points will not exceed d?


-----Input-----

The first line contains two integers n and d (1 ≤ n ≤ 100, 0 ≤ d ≤ 100) — the amount of points and the maximum allowed diameter respectively.

The second line contains n space separated integers (1 ≤ x_{i} ≤ 100) — the coordinates of the points.


-----Output-----

Output a single integer — the minimum number of points you have to remove.


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

Output
1

Input
3 0
7 7 7

Output
0

Input
6 3
1 3 4 6 9 10

Output
3



-----Note-----

In the first test case the optimal strategy is to remove the point with coordinate 4. The remaining points will have coordinates 1 and 2, so the diameter will be equal to 2 - 1 = 1.

In the second test case the diameter is equal to 0, so its is unnecessary to remove any points. 

In the third test case the optimal strategy is to remove points with coordinates 1, 9 and 10. The remaining points will have coordinates 3, 4 and 6, so the diameter will be equal to 6 - 3 = 3.

Difficulty: EASY
Tags: Complete search

Sorting

Greedy algorithms
Skill types: Complete search

Sorting

Greedy algorithms

Starter code:

Solutions:
(n, d) = list(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
c = 0
t = 0
l = []
a.sort()
for i in range(0, n):
	t = 0
	for j in range(i, n):
		x = a[j] - a[i]
		if x <= d:
			t += 1
	l.append(t)
print(n - max(l))


(n, d) = input().split()
n = int(n)
d = int(d)
l = [int(x) for x in input().split()]
l.sort()
mindel = 0
mini = 0
maxi = n - 1
for i in range(n):
	for j in range(n - 1, -1, -1):
		if abs(l[j] - l[i]) <= d and abs(j - i) > mindel:
			mini = i
			maxi = j
			mindel = abs(j - i)
if abs(l[maxi] - l[mini]) > d:
	print(n - 1)
else:
	print(mini + n - maxi - 1)


from itertools import combinations
(n, d) = map(int, input().split())
n1 = n
a = list(map(int, input().split()))
ans = n - 1
a.sort()
for (i, j) in combinations(range(n), 2):
	if abs(a[i] - a[j]) <= d:
		if ans > n - (abs(j - i) + 1):
			ans = n - (abs(j - i) + 1)
print(ans)


from os import path
if path.exists('C:/Users/prana/Desktop/sublime/input.txt'):
	import sys
	sys.stdin = open('C:/Users/prana/Desktop/sublime/input.txt', 'r')
	sys.stdout = open('C:/Users/prana/Desktop/sublime/output.txt', 'w')

def solve(test_case):
	d = int(input().split()[1])
	a = list(map(int, input().split()))
	print(min((sum((1 - (0 <= c - p <= d) for c in a)) for p in a)))
test_case = 1
while test_case:
	solve(test_case)
	test_case -= 1


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
print(min((sum((1 - (0 <= c - p <= d) for c in a)) for p in a)))


(n, d) = map(int, input().split(' '))
x = input().split(' ')
x = [int(i) for i in x]
x = sorted(x)
if n <= 1:
	print(0)
else:
	m = 0
	for i in range(0, n):
		for j in range(i, n):
			if x[j] - x[i] <= d:
				m = max(m, j - i + 1)
	print(n - m)


(q, w) = map(int, input().split())
a = list(map(int, input().split()))
s = [0 for i in range(0, q)]
a.sort()
for i in range(0, q - 1):
	j = i + 1
	while a[j] - a[i] <= w:
		s[i] += 1
		j += 1
		if j == q:
			break
print(q - max(s) - 1)


(n, d) = map(int, input().split())
x = [e for e in map(int, input().split())]
x = sorted(x)
max_contain = 0
for i in range(n):
	head = x[i]
	tail = head + d
	contain = 0
	for j in range(n - i):
		if x[i + j] <= tail:
			contain += 1
		else:
			break
	max_contain = contain if contain > max_contain else max_contain
print(n - max_contain)


def multi():
	inp = input().split(' ')
	(k, d) = (int(inp[0]), int(inp[1]))
	l = list(map(int, input().split(' ')))
	result = len(l)
	l.sort()
	for i in range(0, len(l)):
		for j in range(len(l) - 1, i - 1, -1):
			diam = abs(l[i] - l[j])
			if diam <= d:
				subResult = len(l) - (j - i + 1)
				if result > subResult:
					result = subResult
					break
	print(result)
	return
multi()


(n, d) = map(int, input().split())
x = sorted(list(map(int, input().split())))
for i in range(n):
	if min((x[n - i - 1 + j] - x[j] for j in range(i + 1))) <= d:
		print(i)
		exit(0)


def main():
	(N, D) = map(int, input().split())
	X = tuple(map(int, input().split()))
	cnt = []
	apnd = cnt.append
	x = sorted(X, reverse=1)
	for i in range(N - 1):
		for j in range(i + 1, N):
			if x[i] - x[j] <= D:
				apnd(i + (N - (j + 1)))
	if not cnt:
		print(N - 1)
	else:
		print(min(cnt))
main()


(n, d) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
ans = 10000
for i in range(0, n):
	for j in range(i + 1, n):
		if abs(a[j] - a[i]) <= d:
			ans = min(ans, n - (j + 1) + i)
if ans == 10000:
	print(n - 1)
else:
	print(ans)


global dp

def solve(a, l, r, d):
	if r - l + 1 <= 1:
		return 0
	curD = a[r] - a[l]
	if curD <= d:
		return 0
	if dp[l][r] != -1:
		return dp[l][r]
	dp[l][r] = min(1 + solve(a, l + 1, r, d), 1 + solve(a, l, r - 1, d))
	return dp[l][r]

def greedy(a, d):
	n = len(a)
	ans = 10000
	for i in range(n - 1):
		for j in range(i + 1, n):
			curD = a[j] - a[i]
			if curD <= d:
				pointsRemoved = i + n - j - 1
				ans = min(ans, pointsRemoved)
	if ans == 10000:
		if len(a) == 1:
			return 0
		return len(a) - 1
	return ans
dp = [[-1 for i in range(100)] for j in range(100)]
(n, d) = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
ans = greedy(a, d)
print(ans)


(n, d) = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()
ans = [[1000000000] * n for i in range(n)]
for l in range(n):
	for r in range(l, n):
		if max(a[l:r + 1]) - min(a[l:r + 1]) <= d:
			ans[l][r] = l + (n - r - 1)
print(min([min(i) for i in ans]))


(n, d) = (int(x) for x in input().split())
elems = [int(x) for x in input().split()]
ans = 101
for l in range(0, 101):
	r = l + d
	outside = 0
	for elem in elems:
		if elem < l or elem > r:
			outside += 1
	ans = min(ans, outside)
print(ans)


(n, d) = map(int, input().split())
L = list(map(int, input().split()))
L.sort()
max = -1
for i in range(n):
	for j in range(i, n):
		if L[j] - L[i] <= d:
			if j - i > max:
				max = j - i
print(n - max - 1)


(n, d) = list(map(int, input().split()))
po = list(map(int, input().split()))
po.sort()
tol = []
if n > 1:
	for item in po[0:len(po) - 1]:
		h = 0
		lo = po.index(item)
		for x in po[lo + 1:]:
			if x - item > d:
				ta = po.index(x)
				sa = ta - 1
				tol.append(len(po) - 1 - sa + lo)
				h = 1
				break
			else:
				pass
		if h == 0:
			tol.append(lo)
		po[lo] = 5555
else:
	pass
if tol == list():
	print('0')
else:
	print(min(tol))


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


from math import *
(n, d) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
x = inf
for i in range(n - 1):
	for j in range(i + 1, n):
		c = l[j] - l[i]
		if c <= d:
			x = min(x, n - (j - i + 1))
print(min(n - 1, x))


import logging.config
import sys
logger = logging.getLogger(__name__)

def main():
	(n, d) = (int(x) for x in sys.stdin.readline().split())
	input_array = [int(x) for x in sys.stdin.readline().split()]
	input_array.sort()
	if n == 1:
		print('0')
		return
	result = n - 1
	for i in range(0, n - 1):
		for j in range(i + 1, n):
			if input_array[j] - input_array[i] <= d:
				if i + (n - 1 - j) < result:
					result = i + (n - 1 - j)
	print('{}'.format(result))
main()


def find(points, i, j):
	if i >= j:
		return 0
	if points[j] - points[i] > diameter:
		result1 = find(points, i + 1, j) + 1
		result2 = find(points, i, j - 1) + 1
		return min(result1, result2)
	else:
		return 0
pairs = [int(s) for s in input().split(' ')]
num = pairs[0]
diameter = pairs[1]
points = [int(s) for s in input().split(' ')]
points.sort()
answer = 101
for i in range(num):
	cur = points[i]
	point = next((x[0] for x in enumerate(points) if x[1] > cur + diameter), num)
	answer = min(answer, i + num - point)
print(answer)


(n, d) = map(int, input().split())
A = sorted([int(x) for x in input().split()])
result = n
for i in range(n):
	for j in range(i, n):
		if A[j] - A[i] <= d:
			result = min([result, i + n - j - 1])
print(result)


rd = lambda : map(int, input().split())
(n, d) = rd()
a = sorted(list(rd()))
print(n - max((j - i + 1 for i in range(n) for j in range(i, n) if a[j] - a[i] <= d)))


(n, d) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
r = 0
d2 = 0
for i in range(n):
	for j in range(n):
		d2 = l[j] - l[i]
		if d2 <= d and j - i + 1 > r:
			r = j - i + 1
print(n - r)


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

def check(t):
	global n, d, l
	if t == n:
		return True
	if t == 0:
		return l[-1] - l[0] <= d
	for i in range(t + 1):
		le = l[i]
		ri = l[n - t + i - 1]
		if ri - le <= d:
			return True
	return False
L = -1
R = n
while R - L > 1:
	mid = (L + R) // 2
	if check(mid):
		R = mid
	else:
		L = mid
print(R)


import sys
(n, d) = list(map(int, input().split()))
a = list(map(int, input().split()))
if n == 1:
	print(0)
	sys.exit()
a.sort()
m = 0
for i in range(n):
	c = 0
	for j in range(i + 1, n):
		if a[j] - a[i] <= d:
			c += 1
		else:
			break
	m = max(m, 0 if c == 0 else c + 1)
if m == 0:
	print(n - 1)
else:
	print(n - m)


import bisect
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
if a[-1] - a[0] <= k:
	print(0)
else:
	min_cnt = n
	cnt = 0
	for i in range(n - 1):
		min_cnt = min(min_cnt, n - 1 - bisect.bisect_right(a[i + 1:], a[i] + k))
	for i in range(1, n):
		min_cnt = min(min_cnt, i - 1 + bisect.bisect_left(a[:n - i], a[-i] - k))
	print(min_cnt)


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


def main():
	(n, d) = [int(x) for x in input().split(' ')]
	vals = [int(x) for x in input().split(' ')]
	vals.sort()
	ans = n - 1
	for ind_left in range(n):
		for ind_right in range(ind_left, n, 1):
			v = vals[ind_right] - vals[ind_left]
			if v <= d:
				ans = min(ans, n - ind_right + ind_left - 1)
	print(ans)
main()


import sys

def main():
	in_1 = sys.stdin.readline().split()
	n_points = int(in_1[0])
	diam_requerido = int(in_1[1])
	l_numeros = sys.stdin.readline().split()
	l_numeros = [int(x) for x in l_numeros]
	l_numeros.sort()
	l_sumatoria = [0 for i in range(l_numeros[-1] + 1)]
	for i in l_numeros:
		l_sumatoria[i] += 1
	num_eliminar = []
	if l_numeros[-1] - l_numeros[0] <= diam_requerido:
		num_eliminar.append(0)
	else:
		for i in range(1, l_numeros[-1] + 1):
			if diam_requerido + i <= l_numeros[n_points - 1]:
				num_eliminar.append(n_points - sum(l_sumatoria[i:i + diam_requerido + 1]))
			else:
				break
	num_eliminar_min = min(num_eliminar)
	print(num_eliminar_min)
main()


(n, d) = map(int, input().split())
(nums, mx, freq) = (map(int, input().split()), 0, [0 for i in range(105)])
for num in nums:
	freq[num] += 1
for i in range(1, 102):
	freq[i] += freq[i - 1]
d += 1
for i in range(d, 102):
	mx = max(mx, freq[i] - freq[i - d])
print(n - mx)


def find(arr):
	return arr[len(arr) - 1] - arr[0]
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
d = []
for i in range(len(arr) - 1):
	c = 0
	for j in range(i + 1, len(arr)):
		if arr[j] - arr[i] > k:
			d.append(j - i)
			c = 1
			break
	if c == 0:
		d.append(len(arr) - i)
d.append(-1)
if max(d) == -1:
	print(0)
else:
	print(n - max(d))


[n, m] = input().split(' ')
n = int(n)
m = int(m)
line = input().split(' ')
a = []
for i in range(n):
	a.append(int(line[i]))
b = sorted(a)
ans = -9999
for i in range(n):
	for j in range(i, n):
		if b[j] - b[i] <= m:
			ans = max(ans, j - i)
print(n - ans - 1)


(n, d) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
min_res = 1000000000000000000000000000000000000000000000000000000000
for i in range(len(A)):
	for j in range(len(A)):
		if abs(A[i] - A[j]) <= d:
			if min(i, j) + len(A) - max(i, j) - 1 < min_res:
				min_res = min(i, j) + len(A) - max(i, j) - 1
print(min_res)


(noe, maxs) = [int(x) for x in input().split()]
arr1 = [int(x) for x in input().split()]
arr = sorted(arr1)
mins = int(10000000000.0)
for i in range(noe):
	for j in range(i, noe):
		if arr[j] - arr[i] <= maxs:
			if noe - j + i - 1 < mins:
				mins = noe - j + i - 1
print(mins)


(n, d) = map(int, input().split())
temp = [int(x) for x in input().split()]
temp.sort()
if temp[-1] - temp[0] <= d:
	print(0)
else:
	line = []
	for i in range(n - 1):
		for j in range(i + 1, n):
			if temp[j] - temp[i] > d:
				line.append(j - i)
				break
			elif j == n - 1:
				line.append(j - i + 1)
	print(n - max(line))


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 1e+18
for i in range(n):
	for j in range(i, n):
		if a[j] - a[i] <= d:
			ans = min(ans, i + (n - j - 1))
print(ans)


(n, d) = map(int, input().split())
s = list(map(int, input().split()))
s.sort()
sol = -1
for i in range(n):
	for j in range(i, n):
		if s[j] - s[i] <= d:
			if j - i > sol:
				sol = j - i
print(n - sol - 1)


(n, d) = map(int, input().split())
l = list(map(int, input().split()))
max = 0
for i in range(1, 101):
	cnt = 0
	for element in l:
		if element >= i and element <= i + d:
			cnt += 1
	if cnt > max:
		max = cnt
print(n - max)


(n, d) = list(map(int, input().split()))
x = list(map(int, input().split()))[:n]
x.sort()
res = n
for i in range(n):
	if i > 1 and x[i] == x[i - 1]:
		continue
	start = i
	while start > 0 and x[start - 1] == x[i]:
		start -= 1
	finish = i
	while finish < n and x[finish] - x[i] <= d:
		finish += 1
	res = min(res, start + (n - finish))
print(res)


(n, d) = map(int, input().split())
lis = sorted(map(int, input().split()))
ans = 0
for i in range(n):
	for j in range(n):
		if lis[j] - lis[i] <= d:
			ans = max(ans, j - i + 1)
print(n - ans)


import bisect
(n, d) = map(int, input().split())
x = sorted(map(int, input().split()))
if x[-1] - x[0] <= d:
	print('0')
	exit()
res = n
for tst in range(n):
	ind = bisect.bisect_right(x, x[tst] + d)
	if ind <= tst:
		break
	res = min(res, tst + n - ind)
print(res)


import bisect
(n, d) = map(int, input().split())
arr = sorted(list(map(int, input().split())))
max_span = 0
for i in range(n):
	pos = bisect.bisect_right(arr, arr[i] + d, i)
	max_span = max(max_span, pos - i)
print(n - max_span)


(n, d) = map(int, input().split())
ls = list(map(int, input().split()))
lens = len(ls)
ls.sort()
ans = 999999999999999999999999
for left in range(0, lens):
	for right in range(0, lens):
		if right < left:
			continue
		if ls[right] - ls[left] <= d:
			ans = min(lens - 1 - right + left, ans)
print(ans)


a = input().split(' ')
n = int(a[0])
d = int(a[1])
a = input().split(' ')
a = [int(i) for i in a]
a.sort()
j = []
for i in range(len(a)):
	for i2 in range(i, len(a)):
		if a[i2] - a[i] <= d:
			j.append(len(a) - (i2 - i + 1))
print(min(j))


(n, d) = [int(x) for x in input().split(' ')]
a = [int(x) for x in input().split(' ')]
a.sort()
r = n
for p in range(n):
	q = n - 1
	while a[q] - a[p] > d:
		q -= 1
	if n - (q - p + 1) < r:
		r = n - (q - p + 1)
print(r)


def main():
	(n, d) = map(int, input().split())
	x = list(map(int, input().split()))
	x.sort()
	ans = n
	for i in range(n):
		j = i
		while j < n and x[j] - x[i] <= d:
			j += 1
		ans = min(ans, n - (j - i))
	print(ans)
main()


(a, b) = map(int, input().split())
c = list(map(int, input().split()))
c.sort()
if a == 1:
	print(0)
else:
	d = []
	for i in range(a - 1):
		x = c[i] + b
		j = i + 1
		k = 0
		while j < a and c[j] <= x:
			k += 1
			j += 1
		d.append(k)
	print(a - max(d) - 1)


(n, d) = map(int, input().split())
a = [int(x) for x in input().split()]
a.sort()
ans = 0
j = n - 1
ans = 0
i = 0
mv = 10000
for i in range(n):
	for j in range(i, n):
		if a[j] - a[i] <= d:
			if n - j + i - 1 < mv:
				mv = n - j + i - 1
print(mv)


def main():
	(n, d) = map(int, input().split())
	x = sorted((int(c) for c in input().split()))
	(mn, mx) = (x[0], x[-1])
	diam = mx - mn
	if diam <= d:
		print(0)
		return
	res = []
	for i in range(n):
		for j in range(i + 1, n):
			cnt = i + n - j - 1
			if x[j] - x[i] <= d:
				res.append(cnt)
	if res:
		print(min(res))
	else:
		print(n - 1)
main()


(n, d) = map(int, input().strip().split(' '))
a = list(map(int, input().split(' ')))
a = sorted(a)
count = 10 ** 9
Left = 0
Right = 0
while Left < n:
	while Right < n and a[Right] - a[Left] <= d:
		Right = Right + 1
	count = min(count, Left + n - Right)
	Left = Left + 1
print(count)


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
minCost = len(a)
for i in range(len(a) - 1):
	for j in range(i + 1, len(a)):
		if a[j] - a[i] <= d:
			cost = i + (len(a) - j - 1)
			minCost = min(cost, minCost)
print(min(minCost, len(a) - 1) if len(a) > 1 else 0)


from sys import stdin as cin

def main():
	(n, m) = map(int, cin.readline().split())
	a = list(map(int, cin.readline().split()))
	a.sort()
	x = 0
	y = -1
	for i in range(n):
		if a[i] - a[0] > m:
			y = i
			break
	if y == -1:
		print(0)
		return
	o = n - y
	while y < n:
		x += 1
		while y < n and a[y] - a[x] <= m:
			y += 1
		o = min(n - y + x, o)
	print(o)
main()


(n, d) = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
z = n
for i in range(n):
	y = 0
	for j in range(i, n):
		if x[j] - x[i] <= d:
			if n - (j - i) - 1 < z:
				z = n - (j - i) - 1
print(z)


(z, zz, dgraphs, mod) = (input, lambda : list(map(int, z().split())), {}, 10 ** 9 + 7)
from string import *
from collections import *
from queue import *
from sys import *
from collections import *
from math import *
from heapq import *
from itertools import *
from bisect import *
from collections import Counter as cc
from math import factorial as f

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def prime(x):
	p = ceil(x ** 0.5) + 1
	for i in range(2, p):
		if x % i == 0 and x != 2:
			return 0
	return 1

def dfs(u, visit, graph):
	visit[u] = True
	for i in graph[u]:
		if not visit[i]:
			dfs(i, visit, graph)
(n, k) = zz()
l = zz()
ans = 7878788983898
for i in range(n):
	c = 0
	x = l[i]
	for j in l:
		if j - x <= k and j - x >= 0:
			c += 1
	if ans > n - c:
		ans = n - c
print(ans)


(n, d) = map(int, input().split())
t = list(map(int, input().split()))
t.sort()
if n == 1:
	print(0)
else:
	h = 999999999999
	for j in range(n):
		for k in range(j + 1, n):
			if t[k] - t[j] <= d:
				if n - (k - j + 1) < h:
					h = n - (k - j + 1)
	if h == 999999999999:
		print(n - 1)
	else:
		print(h)


(n, r) = map(int, input().split())
dots = list(map(int, input().split()))
dots.sort()
max = 0
for num in range(len(dots)):
	local = 0
	for num2 in range(num, len(dots)):
		if abs(dots[num] - dots[num2]) <= r:
			local += 1
		else:
			break
	if local > max:
		max = local
print(n - max)


line1 = [int(s) for s in input().split(' ')]
line2 = [int(s) for s in input().split(' ')]
n = line1[0]
d = line1[1]
if n == 1:
	print(0)
	exit()
points = line2
points.sort()
i = 0
min = len(points)
while i < len(points) - 1:
	j = i + 1
	while j < len(points):
		if points[j] - points[i] > d:
			break
		j += 1
	if len(points) - (j - i) < min:
		min = len(points) - (j - i)
	i += 1
print(min)


(n, d) = tuple((int(x) for x in input().split()))
multiset = [int(x) for x in input().split()]
multiset.sort()
local_ans = 0
ans = 1000000000.0 + 7
for i in range(len(multiset)):
	for j in range(i + 1, len(multiset)):
		if abs(multiset[i] - multiset[j]) > d:
			local_ans = len(multiset) - j + i
			break
	else:
		local_ans = i
	if local_ans < ans:
		ans = local_ans
print(ans)


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


(n, d) = list(map(int, input().split()))
x = list(map(int, input().split()))
print(min((len([yi for yi in x if yi < xi or xi + d < yi]) for xi in x)))


(n, d) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
count = 0
a.sort()
p = []
for i in range(n):
	q = a[i] + d
	for j in range(n):
		if a[j] <= q and a[j] >= a[i]:
			count += 1
	p.append(n - count)
	count = 0
print(min(p))


from copy import copy
raw = [int(x) for x in input().split(' ')]
n = raw[0]
d = raw[1]
a = [int(x) for x in input().split(' ')]
a = sorted(a)
strat = 0
best = 200
going = True

def dimof(li):
	return li[-1] - li[0]
while strat < 101 and going:
	c = 0
	temp = a.copy()
	for i in range(strat):
		if dimof(temp) <= d:
			break
		del temp[0]
		c += 1
	if going:
		if dimof(temp) <= d:
			going = False
		else:
			while dimof(temp) > d:
				del temp[-1]
				c += 1
	if c < best:
		best = c
	strat += 1
print(best)


(n, d) = [int(i) for i in input().split(' ')]
arr = [int(i) for i in input().split(' ')]
arr = sorted(arr)
res = n - max((j - i + 1 for i in range(n) for j in range(i, n) if arr[j] - arr[i] <= d))
print(res)


def solve(d, A):
	if d == 100:
		return 0
	B = [0] * 101
	for a in A:
		B[a] += 1
	for i in range(1, 101):
		B[i] += B[i - 1]
	M = 0
	for i in range(d + 1, 101):
		u = B[i] - B[i - d - 1]
		M = max(u, M)
	return len(A) - M
(n, d) = map(int, input().split())
a = list(map(int, input().split()))
print(solve(d, a))


(n, d) = map(int, input().split())
ls = list(map(int, input().split()))
ref = 101
count = 0
for i in ls:
	max = i
	for j in ls:
		if i >= j and i - j <= d:
			count = 0
			for k in ls:
				if k < j or k > i:
					count += 1
			if count < ref:
				ref = count
print(ref)


(n, d) = map(int, input().split())
x = sorted(list(map(int, input().split(' '))))
sum = 0
list = []
for i in range(n):
	for j in range(i, n):
		if x[j] - x[i] <= d:
			sum += 1
	list.append(sum)
	sum = 0
print(len(x) - max(list))


(a, b) = map(int, input().split())
r = sorted(map(int, input().split()))
z = j = 0
for i in range(a):
	while j < a and r[j] - r[i] <= b:
		j += 1
	z = max(z, j - i)
print(a - z)


import sys
ReadEncoding = sys.stdin.encoding
WriteEncoding = sys.stdout.encoding
LogEncoding = sys.stderr.encoding
ReadEncoding = 'utf-8'
WriteEncoding = 'utf-8'
LogEncoding = 'utf-8'
PythonVersion = sys.version_info[0]
ReadEncoding = 'bytes'
import logging
import logging.handlers
ReadTarget = None
WriteTarget = None

def convert_to_bytes(arg):
	if PythonVersion < 3:
		if isinstance(arg, bytes):
			return arg
		elif isinstance(arg, str):
			return arg.encode()
		elif hasattr(arg, '__iter__'):
			return b' '.join(map(convert_to_bytes, arg))
		else:
			return bytes(arg)
	else:
		if isinstance(arg, bytes):
			return arg.decode(WriteEncoding)
		elif isinstance(arg, str):
			return arg
		elif hasattr(arg, '__iter__'):
			return ' '.join(map(convert_to_bytes, arg))
		else:
			return str(arg)
		pass
	if isinstance(arg, bytes):
		return arg.decode(WriteEncoding)
	elif isinstance(arg, str):
		return arg
	elif hasattr(arg, '__iter__'):
		return ' '.join(map(convert_to_bytes, arg))
	else:
		return str(arg)

class edx_in:

	def __init__(self, target=None):
		self.target = target

	def create_lineTokenizer(self):
		if self.mm:
			for line in iter(self.mm.readline, ''):
				yield line
		else:
			for line in iter(self.stream.readline, ''):
				yield line

	def __enter__(self):
		self.mm = None
		self.isFileEmpty = True
		self.stream = sys.stdin
		self.lines = self.create_lineTokenizer()
		self.lineTokens = None
		return self

	def __exit__(self, type, value, traceback):
		if not self.isFileEmpty:
			if self.mm:
				self.mm.close()
			self.stream.close()

	def next_line(self):
		ret = None
		try:
			if ReadEncoding == 'bytes':
				ret = b' '.join(self.lineTokens)
				if ret == b'':
					raise ValueError()
			else:
				ret = ' '.join(self.lineTokens)
				if ret == '':
					raise ValueError()
		except (ValueError, TypeError) as e:
			self.lineTokens.close()
			if hasattr(self.lines, 'next'):
				ret = self.lines.next()
			if hasattr(self.lines, '__next__'):
				ret = self.lines.__next__()
			pass
		finally:
			if ReadEncoding == 'bytes':
				ret = ret
			else:
				ret = ret.decode(ReadEncoding)
			return ret

	def next_int(self):
		return int(self.next_token())

	def next_float(self):
		return float(self.next_token())

	def next_str(self):
		ret = self.next_token()
		if isinstance(ret, bytes):
			return ret.decode()
		return ret

	def getLineTokens(self, line):
		for token in iter(line.split()):
			yield token

	def nextNToken(self, rep=0):
		ans = []
		while rep > 0:
			ans.append(self.next_token())
			rep -= 1
		return ans

	def next_token(self):
		try:
			if hasattr(self.lineTokens, 'next'):
				ret = self.lineTokens.next()
			if hasattr(self.lineTokens, '__next__'):
				ret = self.lineTokens.__next__()
			return ret
		except:
			self.lineTokens = self.getLineTokens(self.next_line())
			return self.next_token()

class edx_out:

	def __init__(self, target=None):
		self.target = target

	def __enter__(self):
		import platform
		self.is_cpython = platform.python_implementation() == 'CPython'
		if False:
			pass
		else:
			self.stream = sys.stdout
		return self

	def __exit__(self, type, value, traceback):
		pass

	def write(self, arg):
		self.stream.write(convert_to_bytes(arg))

	def writeln(self, arg):
		if WriteEncoding == 'bytes':
			self.write(b'\n')
		else:
			self.write('\n')

	def test(this, expression):
		frame = sys._getframe(1)
		exp = expression
		ans = repr(eval(exp, frame.f_globals, frame.f_locals))
		if WriteEncoding == 'bytes':
			this.debug(b'test : ' + exp.encode(WriteEncoding) + b' = ' + ans.encode(WriteEncoding))
		else:
			this.debug('test : ' + exp + ' = ' + ans)
		pass
sys.setrecursionlimit(100)

def solve():
	debug('ssss')

	def cf940a():
		(n, d) = (ri(), ri())
		arr = []
		for i in range(n):
			arr.append(ri())
		arr.sort()
		start = 0
		target = start
		maxCount = 0
		curCount = 0
		for start in range(len(arr)):
			cnt = 1
			target = start
			while True:
				debug(arr)
				debug(start, target, arr[start], arr[target], cnt)
				cnt += 1
				target += 1
				if target >= len(arr):
					cnt -= 1
					break
				if arr[target] - arr[start] > d:
					cnt -= 1
					break
			if cnt > maxCount:
				maxCount = cnt
			if target >= len(arr):
				break
			pass
			pass
		debug('max : ', maxCount)
		put(len(arr) - maxCount)
		pass
	cf940a()
	pass
try:
	logger1 = logging.getLogger('log1')
	debug = lambda *x: logger1.log(logging.DEBUG, convert_to_bytes(x))
	PutLevel = 100
	logging.PUT = PutLevel
	logging.addLevelName(PutLevel, 'PUT')
	logger1.setLevel(logging.PUT)
	formatter = logging.Formatter()
except:
	pass
with edx_in(ReadTarget) as Reader, edx_out(WriteTarget) as Writer:
	try:
		outHandler = logging.StreamHandler(Writer.stream)
		outHandler.setFormatter(formatter)
		logger1.addHandler(outHandler)
		if PythonVersion >= 3:
			put = lambda *args: logger1.log(logging.PUT, convert_to_bytes(args))
			info = lambda *args: logger1.log(logging.INFO, convert_to_bytes(args))
			critical = lambda *args: logger1.log(logging.CRITICAL, convert_to_bytes(args))
		else:
			put = lambda *args: logger1.log(logging.PUT, convert_to_bytes(args))
			info = lambda *args: logger1.log(logging.INFO, convert_to_bytes(args))
			critical = lambda *args: logger1.log(logging.CRITICAL, convert_to_bytes(args))
	except ModuleNotFoundError:
		debug = Writer.writeln
		put = Writer.writeln
		info = Writer.writeln
		critical = Writer.writeln

	def nop(*arg):
		pass
	debug = nop
	test = nop
	info = nop
	reader = Reader
	writer = Writer
	ri = reader.next_int
	rs = reader.next_str
	rt = reader.next_token
	rf = reader.next_float
	rl = reader.next_line
	rnt = reader.nextNToken
	wl = writer.writeln
	solve()


def memoize(f):
	memo = {}

	def helper(*x):
		x = tuple(x)
		if x not in memo:
			memo[x] = f(*x)
		return memo[x]
	return helper
(n, d, *_) = list(map(int, input().split()))
(*x,) = list(map(int, input().split()))
x.sort()

@memoize
def solve(d, li, ri):
	if x[ri] - x[li] <= d:
		return 0
	else:
		return min(solve(d, li + 1, ri), solve(d, li, ri - 1)) + 1
print(solve(d, 0, len(x) - 1))


(n, d) = map(int, input().split())
s1 = input()
s = list(map(int, s1.split()))
s_res = [[] for i in range(n)]
s.sort()
for i in range(len(s)):
	for j in range(len(s)):
		if abs(int(s[j]) - int(s[i])) <= d and int(s[i]) <= int(s[j]):
			s_res[i].append(int(s[j]))
l = -1
for i in range(n):
	if len(s_res[i]) > l:
		l = len(s_res[i])
print(n - l)


import sys
(n, d) = [int(x) for x in input().split()]
lst = [int(x) for x in input().split()]
lst.sort()
z = 0
if max(lst) - min(lst) == d:
	print(0)
	sys.exit()
for i in range(n):
	for j in range(i + 1, n + 1):
		lst1 = lst[i:j]
		if max(lst1) - min(lst1) <= d and z <= len(lst1):
			z = len(lst1)
print(n - z)


(n, d) = [int(i) for i in input().split()]
l = [int(i) for i in input().split()]
l.sort()
mymap = {}
max = 0
for i in range(n):
	sol = 1
	x = l[i]
	for j in range(n):
		if j != i and abs(x - l[j]) <= d and (l[j] >= x):
			sol += 1
	if sol > max:
		max = sol
print(n - max)


from sys import stdin, stdout

def rint():
	return list(map(int, stdin.readline().split()))
x = [0 for i in range(101)]
(n, d) = rint()
xin = list(rint())
xin.sort()
for xx in xin:
	x[xx] += 1
if xin[-1] <= d + 1:
	print(0)
	return
maxn = 0
for i in range(1, d + 2):
	maxn += x[i]
cur = maxn
for i in range(d + 2, 101):
	cur = cur - x[i - d - 1] + x[i]
	if cur > maxn:
		maxn = cur
print(n - maxn)


(a, b) = map(int, input().split())
c = list(map(int, input().split()))
d = sorted(c)
e = 0
for _ in range(a):
	for i in range(a):
		if _ < i:
			if d[i] - d[_] <= b:
				e = max(e, i - _)
print(a - e - 1)


(n, d) = (int(x) for x in input().split())
a = sorted([int(x) for x in input().split()])
min = n
for i in range(n):
	for j in range(n - 1, i, -1):
		if a[j] - a[i] <= d and n - j + i < min:
			min = n - j + i
print(min - 1)


def find_maxdiff(xs, d):
	maxdiff_idx = 0
	diffs = [0 for i in range(len(xs))]
	for i in range(len(xs) - 1):
		for j in range(i + 1, len(xs)):
			if abs(xs[i] - xs[j]) > d:
				for s in (i, j):
					diffs[s] += 1
					if diffs[s] > diffs[maxdiff_idx]:
						maxdiff_idx = s
	return maxdiff_idx if diffs[maxdiff_idx] else None

def main():
	(n, d) = [int(x) for x in input().split()]
	xs = [int(x) for x in input().split()]
	count = 0
	maxdiff_idx = find_maxdiff(xs, d)
	while maxdiff_idx is not None:
		count += 1
		xs.pop(maxdiff_idx)
		maxdiff_idx = find_maxdiff(xs, d)
	print(count)
main()


in1 = input()
in_str = in1.split()
n = int(in_str[0])
diameter = int(in_str[1])
points = sorted(list(map(int, input().split())))
longest = 0
start = 0
for start in range(n):
	length = 0
	end = start
	while diameter >= points[end] - points[start] and end < n - 1:
		end += 1
	if diameter < points[end] - points[start]:
		length = end - start
	else:
		length = end - start + 1
	if length > longest:
		longest = length
print(n - longest)


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
maximum = n - 1
for i in range(n):
	for j in range(i + 1, n):
		if l[j] - l[i] <= k:
			if n - (j - i + 1) < maximum:
				maximum = n - (j - i + 1)
print(maximum)


def main():
	(n, d) = map(int, input().split())
	l = sorted(map(int, input().split()))
	(b, j, r) = (l[0], 0, 0)
	for (i, a) in enumerate(l):
		if a - b > d:
			a -= d
			while a > l[j]:
				j += 1
			b = l[j]
		elif r < i - j:
			r = i - j
	print(n - r - 1)
main()


n = input().split(' ')
n1 = int(n[0])
n2 = int(n[1])
a = input().split(' ')
d2 = 0
d = 0
lol = 0
for i in range(len(a)):
	a[i] = int(a[i])
a.sort()
for i in range(len(a)):
	for h in range(len(a)):
		if a[h] - a[i] <= n2 and h - i > lol:
			lol = h - i
print(n1 - lol - 1)


import sys
import string
from collections import Counter, defaultdict
from math import fsum, sqrt, gcd, ceil, factorial
from operator import add
from bisect import *
inf = float('inf')
flush = lambda : sys.stdout.flush
comb = lambda x, y: factorial(x) // factorial(y) // factorial(x - y)
ip = lambda : input()
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())
(n, k) = r()
arr = rr()
arr.sort()
ans = inf
for i in range(n):
	need = arr[i] + k
	ans = min(i + n - bisect(arr, need), ans)
print(ans)


from sys import stdin, stdout
from random import randrange
(n, d) = map(int, stdin.readline().split())
points = sorted(list(map(int, stdin.readline().split())))
ans = n
for i in range(n):
	for j in range(n - 1, i - 1, -1):
		if points[j] - points[i] <= d:
			ans = min(ans, n - (j - i + 1))
stdout.write(str(ans))


(n, d) = map(int, input().split())
l = [int(x) for x in input().split()]
best = 200
for item in l:
	m = len([x for x in l if x < item or x > item + d])
	best = min(m, best)
print(best)


(n, k) = map(int, input().split())
(a, l) = (sorted(map(int, input().split())), 0)
for i in range(n):
	for j in range(n):
		if i < j and a[j] - a[i] <= k:
			l = max(l, j - i)
print(n - l - 1)


(n, x) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
res = 100000000000
for i in range(n):
	for j in range(i, n):
		if arr[j] - arr[i] <= x:
			res = min(res, n - (abs(i - j) + 1))
print(res)


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
count = [0 for i in range(102)]
for i in range(n):
	count[a[i]] += 1
sum2 = [0 for i in range(200)]
for i in range(1, 101):
	sum2[i] = sum(count[i - 1:i + d])
max1 = (0, 0)
for i in range(len(sum2)):
	if max1[1] < sum2[i]:
		max1 = (i, sum2[i])
print(n - max1[1])


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
ans = n - 1
a.sort()
for l in range(n):
	for r in range(l, n):
		if a[r] - a[l] <= d:
			ans = min(ans, l - 1 + (n - r))
print(ans)


(n, d) = list(map(int, input().split()))
l = list(map(int, input().split()))
l.sort()
found = 0
for i in range(n, 0, -1):
	if found:
		break
	for j in range(n - i + 1):
		if l[j + i - 1] - l[j] <= d:
			print(n - i)
			found = 1
			break


l = input().split()
n = int(l[0])
b = int(l[1])
l = input().split()
for i in range(len(l)):
	l[i] = int(l[i])
l.sort()
m = []
if len(l) == 1:
	print(0)
else:
	for i in range(n):
		if not i == n - 1:
			for j in range(i + 1, n):
				if l[j] - l[i] <= b:
					m.append(i + (n - j) - 1)
	if m == []:
		print(n - 1)
	else:
		print(min(m))


import bisect
(n, d) = list(map(int, input().split()))
multiset = list(map(int, input().split()))
multiset.sort()
ans = 0
for (i, x) in enumerate(multiset):
	ans = max(ans, bisect.bisect_right(multiset, x + d) - i)
print(n - ans)


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
temp = []
for i in range(len(a)):
	count = 0
	for j in range(i, len(a)):
		if a[j] - a[i] <= d:
			count += 1
		else:
			break
	temp.append(count)
t = max(temp)
print(len(a) - t)


from sys import *
(n, k) = [int(x) for x in input().split()]
s = input()
d = list()
for x in s.split():
	d.append(int(x))
d.sort()
for i in range(len(d), 0, -1):
	j = 0
	while i + j - 1 < len(d):
		if d[i + j - 1] - d[j] <= k:
			print(len(d) - i)
			exit()
		j += 1


(n, k) = map(int, input().split())
l = [int(i) for i in input().split()]
l.sort()
if max(l) - min(l) <= k:
	print(0)
	exit()
maxlen = 0
for i in range(n):
	for j in range(i, n):
		if max(l[i:j + 1]) - min(l[i:j + 1]) <= k:
			maxlen = max(maxlen, j - i + 1)
print(n - maxlen)


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
c = []
a = sorted(a)
for i in range(len(a)):
	b = 0
	for j in range(i + 1, len(a)):
		if a[j] - a[i] <= d:
			b = b + 1
	b = b + 1
	c.append(n - b)
print(min(c))


(n, d) = map(int, input().strip().split())
x = list(map(int, input().strip().split()))
x.sort()
res = 1000000
for l in range(n):
	for r in range(l, n):
		cur = x[r] - x[l]
		if cur <= d:
			res = min(res, n - (r - l + 1))
print(res)


list_points = [0] * 101
numbers = list(map(int, input().split()))
n = numbers[0]
d = numbers[1]
points = list(map(int, input().split()))
for point in points:
	list_points[point] += 1
max_count = 0
count = 0
for i in range(0, d + 1):
	count = count + list_points[i]
max_count = count
for i in range(d + 1, 101):
	count += list_points[i]
	count -= list_points[i - d - 1]
	if count > max_count:
		max_count = count
ans = n - max_count
print(ans)


def func():
	(n, d) = list(map(int, input().split()))
	a = sorted(list(map(int, input().split())))
	if n == 1:
		return 0
	m_count = float('inf')
	for i in range(n - 1):
		j = i + 1
		count = n - 1
		while j < n and a[j] - a[i] <= d:
			count -= 1
			j += 1
		if count < m_count:
			m_count = count
	return m_count
print(func())


(n, k) = map(int, input().split())
l = sorted(list(map(int, input().split()))) + [100000]
a = 0
for i in range(n + 1):
	u = 1
	for j in range(i + 1, n + 1):
		if l[j] - l[i] <= k:
			u += 1
		else:
			a = max(a, u)
			u = 0
print(n - a)


(n, d) = list(map(int, input().split()))
x = sorted(map(int, input().split()))
max_num = 1
for i in range(len(x)):
	flag = True
	for j in range(i + 1, len(x)):
		if x[j] - x[i] > d:
			if j - i > max_num:
				max_num = j - i
			flag = False
			break
	if flag:
		if len(x) - i > max_num:
			max_num = len(x) - i
print(len(x) - max_num)


def solve(n, d, arr):
	tempLen = 0
	for i in range(n):
		for j in range(i, n):
			tempdiff = abs(arr[j] - arr[i])
			templen = j - i + 1
			if tempdiff <= d and templen >= tempLen:
				tempLen = templen
	print(n - tempLen)

def run():
	(n, d) = map(int, input().split())
	arr = list(map(int, input().split()))
	if len(arr) == 1:
		print(0)
	else:
		arr.sort()
		solve(n, d, arr)
run()


(n, d) = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
(lo, ans, cur, idx) = (A[0], 1, 1, 0)
A.sort()
ans = 0
for i in range(0, n):
	cur = 0
	for j in range(i, n):
		if A[j] - A[i] <= d:
			cur = cur + 1
		else:
			break
		ans = max(cur, ans)
print(n - ans)


import math

def inp():
	a = input().split()
	return list(map(int, a))

def C(R, x1, y1, x2, y2):
	dy = y2 - y1
	dx = x2 - x1
	l = math.sqrt(dx ** 2 + dy ** 2)
	if l == 0:
		print(x1, y1 + R / 2, R / 2)
		return 0
	if l > R:
		print(x1, y1, R)
		return 0
	r = (l + R) / 2
	c = R - r
	yp = dy / l * (l + c) - y2 + y1
	xp = (l + c) * dx / l - x2 + x1
	x = x1 - xp
	y = y1 - yp
	print(x, y, r)

def inpt():
	n = input().split()
	(n, d) = list(map(int, n))
	a = input().split()
	return (n, d, list(map(int, a)))

def multifind(n, d, A):
	A.sort()
	dmin = 0
	j = 0
	i = 0
	while i < n:
		mas = i - j + 1
		if A[i] - A[j] <= d:
			if mas > dmin:
				dmin = mas
		else:
			j += 1
			i -= 1
		i += 1
	print(n - dmin)
multifind(*inpt())


nd = input().split(' ')
(n, d) = (int(nd[0]), int(nd[1]))
points = input().split(' ')
for p in range(len(points)):
	points[p] = int(points[p])
points.sort()
to_remove = []
l = len(points)
for i in range(l):
	for j in range(l):
		if abs(points[i] - points[j]) <= d:
			to_remove.append(l - (i - j + 1))
print(min(to_remove))


(n, d) = list(map(int, input().split()))
a = list(map(int, input().split()))
a = sorted(a)
l = 0
r = 0
cur_d = a[r] - a[l]
max_num = 1
while r < len(a):
	if a[r] - a[l] <= d:
		max_num = max(max_num, r - l + 1)
		r += 1
	else:
		l += 1
print(len(a) - max_num)


(n, d) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
dia = arr[-1] - arr[0]
deletions = n - 1
for i in range(n):
	for j in range(i, n):
		temp_dia = arr[j] - arr[i]
		temp_del = i + n - 1 - j
		if temp_dia <= d and temp_del < deletions:
			dia = temp_dia
			deletions = temp_del
print(deletions)


(n, d) = [int(c) for c in input().split()]
a = [0]
b = [int(x) for x in input().split()]
for i in b:
	a.append(i)
a.sort()
ans = 10 ** 9
for i in range(1, n + 1):
	now = n - 1
	for j in range(i + 1, n + 1):
		if a[j] - a[i] <= d:
			now -= 1
	ans = min(ans, now)
print(ans)


str1 = input()
str2 = input()
a = str1.split(' ')
b = str2.split(' ')
(n, d) = (int(a[0]), int(a[1]))
multiset = []
for i in b:
	multiset.append(int(i))
multiset.sort()
maximum = 1
for i in range(1, n):
	j = i - 1
	count = 1
	while j >= 0 and abs(multiset[i] - multiset[j]) <= d:
		count += 1
		j -= 1
	if count > maximum:
		maximum = count
print(n - maximum)


(n, d) = map(int, input().split())
A = list(map(int, input().split()))
d = d + 1
B = []
for q in range(101):
	B.append(0)
for q in range(n):
	B[A[q]] += 1
res = 0
for q in range(d):
	res = res + B[q]
ans = res
for q in range(d, 101):
	res = res + B[q] - B[q - d]
	ans = max(res, ans)
print(n - ans)


import math
(n, d) = map(int, input().split())
a = map(int, input().split())
a = sorted(list(a))
n = len(a)
ans = 0
for i in range(n):
	tot = 1
	for j in range(i + 1, n):
		if a[j] - a[i] > d:
			break
		tot += 1
	ans = max(ans, tot)
print(n - ans)


(n, d) = map(int, input().split())
A = [int(i) for i in input().split()]
print(min((sum((c < p or p < c - d for c in A)) for p in A)))


(n, d) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
i = 0
j = 1
l = 0
tl = 1
if n == 1:
	print(0)
	exit()
while True:
	if abs(a[i] - a[j]) <= d:
		tl += 1
		j += 1
	else:
		if tl > l:
			l = tl
		tl = 1
		i += 1
		j = i + 1
	if i >= n - 1 or j >= n:
		if tl > l:
			l = tl
		break
print(n - l)


(n, d) = map(int, input().split())
x = list(map(int, input().split()))
print(min((sum((i - j > d or i < j for i in x)) for j in x)))


(n, d) = map(int, input().split())
arr = [int(x) for x in input().split()]
arr.sort()
start = 0
end = 0
mx = 0
while end < n:
	while end < n and arr[end] - arr[start] <= d:
		end += 1
	mx = max(mx, end - start)
	start += 1
mx = max(mx, n - start)
print(n - mx)


(n, d) = [int(k) for k in input().split(' ') if k]
f = sorted([int(k) for k in input().split(' ') if k])
pairs = [[] for i in range(n + 1)]
bad = 0
for a in range(n):
	for b in range(a, n):
		if f[b] - f[a] > d:
			pairs[a].append(b)
			pairs[b].append(a)
			bad += 1
count = 0
while bad > 0:
	maximum = 0
	where = -1
	for i in range(len(pairs)):
		if maximum < len(pairs[i]):
			maximum = len(pairs[i])
			where = i
	count += 1
	bad -= maximum
	for i in range(len(pairs)):
		if where in pairs[i]:
			del pairs[i][pairs[i].index(where)]
	pairs[where] = []
print(count)


(n, d) = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
x.sort()
hsh = []
pos = 0
l = len(x)
tmp = -1
for i in range(101):
	if x[pos] == i:
		for pos1 in range(pos, l):
			if x[pos] == x[pos1]:
				tmp += 1
			else:
				break
		pos = pos1
	hsh.append(tmp)
mx = 0
for i in range(l):
	if x[i] + d > 100:
		mx = max(mx, l - i)
		break
	if hsh[x[i] + d] - i + 1 > mx:
		mx = hsh[x[i] + d] - i + 1
print(max(0, l - mx))


x = input()
x = x.split(' ')
n = int(x[0])
d = int(x[1])
x = input()
x = x.split(' ')
for i in range(n):
	x[i] = int(x[i])
x.sort()
l = []
for i in range(0, n):
	for j in range(i + 1, n):
		if x[j] - x[i] <= d:
			l.append(i + (n - j) - 1)
if l == []:
	print(n - 1)
else:
	print(min(l))


a = [*map(int, input().split(' '))]
b = [*map(int, input().split(' '))]
b = sorted(b)
c = 0
d = 0
e = 0
f = len(b)
for i in range(0, f):
	for j in range(i, f):
		if b[j] - b[i] > a[1]:
			c += 1
			i += 1
		if j == f - 1:
			break
	if j == f - 1:
		break
print(c)


(n, d) = [int(s) for s in input().split(' ')]
x = [int(s) for s in input().split(' ')]
x.sort()
m = float('inf')
for i in range(n):
	for j in range(i, n):
		if x[j] - x[i] <= d:
			m = min(m, n - (j - i + 1))
print(m)


useless = input().split()
n = int(useless[1])
ans = []
list1 = list(map(int, input().split()))
lis = sorted(list1)
if max(lis) - min(lis) <= n:
	print(0)
else:
	for i in range(len(lis)):
		for j in range(0, i + 1):
			if lis[i] - lis[j] <= n:
				ans += [len(lis) - (i - j + 1)]
	print(min(ans))


(n, r) = map(int, input().split())
a = map(int, input().split())
flag = 0
a = sorted(a)
d = 0
for i in range(n):
	for j in range(i, n):
		if a[j] - a[i] <= r:
			d = max(d, j - i + 1)
print(n - d)


(n, k) = map(int, input().split())
b = [0] * 101
a = list(map(int, input().split()))
for i in a:
	b[i] += 1
c = max = 0
for i in range(101 - k):
	c = sum(b[i:i + k + 1])
	if max < c:
		max = c
print(n - max)


(number, diameter) = [int(x) for x in input().split()]
numbers = [int(x) for x in input().split()]
numbers.sort()
max_covered = 0
for i in range(len(numbers)):
	j = i
	while j != len(numbers) and abs(numbers[i] - numbers[j]) <= diameter:
		j += 1
	max_covered = max(j - i, max_covered)
print(len(numbers) - max_covered)


from collections import Counter
(n, d) = map(int, input().split())
x = list(map(int, input().split()))
c = Counter(x)
l = sorted(c.keys())
(a, b) = (0, 1)
s_d = 0
s_p = c[l[0]]
m = c[l[0]]
ln = len(l)
for i in range(2 * ln):
	if s_d < d:
		if b < ln:
			s_d += l[b] - l[b - 1]
			s_p += c[l[b]]
			b += 1
		if s_d <= d:
			m = max(m, s_p)
	elif a + 1 < ln:
		s_d -= l[a + 1] - l[a]
		s_p -= c[l[a]]
		a += 1
print(n - m)


(n, d) = map(int, input().split())
numbers = list(map(int, input().split()))
cnt = 0
numbers = sorted(numbers)
w = 0
for i in range(n):
	j = i
	while j < n and numbers[j] - numbers[i] <= d:
		j += 1
	if w < j - i:
		w = j - i
print(n - w)


def D(a):
	return a[-1] - a[0]
(n, d) = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()
m = 1000
for i in range(0, n):
	for j in range(i, n):
		if D(a[i:j + 1]) <= d:
			m = min(m, n - len(a[i:j + 1]))
print(m)


import sys
lines = sys.stdin.readlines()
(n, d) = map(lambda x: int(x), lines[0].split())
sequence = [int(x) for x in lines[1].split()]

def rank(arr):
	to_rank = []
	for (idx, no) in enumerate(arr):
		greate_d = 0
		for no_2 in arr:
			if abs(no - no_2) > d:
				greate_d = greate_d + 1
		to_rank.append((idx, greate_d))
	to_rank = sorted(to_rank, reverse=True, key=lambda x: x[1])
	return to_rank
invalid = True
counter = 0
while invalid:
	results = rank(sequence)
	if results[0][1] == 0:
		invalid = False
		break
	del sequence[results[0][0]]
	counter = counter + 1
print(counter)


(x, y) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
cnt = 0
mx = 0
val = 0
for i in range(x):
	for j in range(i, x):
		z = abs(a[i] - a[j])
		if z <= y:
			cnt = cnt + 1
	mx = max(cnt, mx)
	cnt = 0
print(x - mx)


from functools import *
from time import time

def measure_time(fun):

	def wrapper(*args, **kwargs):
		begin = time()
		rv = fun(*args, **kwargs)
		end = time()
		print(end - begin)
		return rv
	return wrapper

def our_cache(func):
	memo = [-1] * (max + 1)

	@wraps(func)
	def wrapper(arg):
		if memo[arg] == -1:
			memo[arg] = func(arg)
		return memo[arg]
	return wrapper

def main():
	(n, d) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	max_l = 0
	for i in arr:
		l = 0
		for j in arr:
			if 0 <= j - i <= d:
				l += 1
		max_l = max(max_l, l)
	print(len(arr) - max_l)
main()


(n, d) = map(int, input().split())
ns = list(map(int, input().split()))
nss = list(set(ns))
nss.sort()
nsss = []
for i in nss:
	nsss += [(i, ns.count(i))]
nn = len(nsss)
mins = n
for i in range(nn):
	conts = nsss[i][1]
	for j in range(i + 1, nn):
		conts += nsss[j][1]
		new = nsss[j][0] - nsss[i][0]
		if new > d:
			mins = min(mins, n + nsss[i][1] - conts)
		elif new == d:
			mins = min(mins, n - conts)
		else:
			mins = min(mins, n - conts)
			continue
		break
if mins == n:
	print(0)
else:
	print(mins)


(n, d) = map(int, input().split())
c = list(map(int, input().split()))
c = sorted(c)
k = 0
diam = c[-1] - c[0]
while diam > d:
	k += 1
	p = k
	q = 0
	while p >= 0:
		a = c[p:n - q]
		diam = min(diam, a[-1] - a[0])
		p -= 1
		q += 1
print(k)


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
res = n - 1
for i in range(n):
	for j in range(i, n):
		if l[j] - l[i] > k:
			continue
		res = min(res, n - (j - i + 1))
print(res)


fl = input()
sl = input()
(num_points, max_d) = [int(x) for x in fl.split()]
points = sorted([int(x) for x in sl.split()])
first_p = 0
second_p = 1
points_to_rem = num_points - 2
min_points_to_rem = num_points
while second_p < num_points and first_p < num_points:
	if num_points == 1:
		break
	dist = points[second_p] - points[first_p]
	if dist <= max_d:
		min_points_to_rem = min(min_points_to_rem, points_to_rem)
		second_p += 1
		points_to_rem -= 1
	if dist > max_d:
		first_p += 1
		points_to_rem += 1
if num_points == 1:
	print(0)
else:
	print(min_points_to_rem)


(n, d) = map(int, input().split())
c = d
x = list(map(int, input().split()))
x.sort()
(cur_cnt, max_cnt) = (1, 1)
for i in range(n - 1):
	cur_cnt = 1
	for j in range(i + 1, n):
		if x[j] - x[i] <= d:
			cur_cnt += 1
		else:
			if cur_cnt > max_cnt:
				max_cnt = cur_cnt
			cur_cnt = 1
	max_cnt = max(cur_cnt, max_cnt)
print(n - max_cnt)


(n, d) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
a.append(0)
ans = n + 1
if max(a) - min(a) <= d:
	print(0)
else:
	for i in range(n):
		for j in range(n + 1):
			na = a[i:j]
			if len(na) > 0 and max(na) - min(na) <= d:
				ans = min(ans, i + n - j)
	print(ans)


import sys
(n, d) = map(int, input().split())
l = [int(x) for x in input().split()]
l.sort()
m = 0
for i in range(n):
	c = 0
	for z in range(i, n):
		if l[z] - l[i] > d:
			break
		c += 1
	m = max(m, c)
print(n - m)


(n, d) = map(int, input().split())
point_array = list(map(int, input().split()))
point_array.sort()
max_len = 0
for i in range(0, n):
	for j in range(i, n):
		if point_array[j] - point_array[i] <= d:
			if j - i + 1 > max_len:
				max_len = j - i + 1
			if i == j and max_len == 0:
				max_len = 1
print(n - max_len)


inf = 4557430888798830399
M = mod = 1000000007
mod2inv = 500000004
pt = lambda *a, **k: print(*a, **k, flush=True)
rd = lambda : map(int, input().split())
(n, d) = rd()
a = list(rd())
a.sort()
r = 0
for i in range(n):
	for j in range(i, n):
		if a[j] - a[i] > d:
			break
		r = max(r, j - i + 1)
print(n - r)


(n, d) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
A = 0
for length in range(n - 1, -1, -1):
	for i in range(n - length):
		if l[i + length] - l[i] <= d:
			A = -1
			print(n - length - 1)
			break
	if A == -1:
		break


(n, d) = [int(x) for x in input().split()]
multiset = [int(x) for x in input().split()]
multiset.sort()
max_inside = -1
for i in range(n):
	for j in range(i, n):
		if multiset[j] - multiset[i] <= d and j - i + 1 > max_inside:
			max_inside = j - i + 1
print(n - max_inside)


from collections import Counter
(n, d) = map(int, input().split())
x = sorted(map(int, input().split()))
freq = list(Counter(x).items())
freq.sort(key=lambda pair: pair[0])
toleft = 0
mindrop = n
for (i, x) in enumerate(freq):
	toleft += freq[i - 1][1] if i > 0 else 0
	toright = sum([pair[1] for pair in freq[i + 1:] if pair[0] > x[0] + d])
	mindrop = min(toleft + toright, mindrop)
print(mindrop)


(n, d) = [int(i) for i in input().split()]
e = [int(i) for i in input().split()]
e.sort()
w = 0
for i in range(n):
	j = i
	while j < n and e[j] - e[i] <= d:
		j += 1
	if w < j - i:
		w = j - i
print(n - w)


import math
(n, d) = map(int, input().split())
ar = list(map(int, input().split()))
ar.sort()
if n == 1:
	ans = 1
else:
	ans = 10000000
for i in range(n):
	for j in range(i, n):
		if ar[j] - ar[i] <= d and n - (j - i) < ans:
			ans = n - (j - i)
print(ans - 1)


(n, k) = map(int, input().strip().split(' '))
lst = list(map(int, input().strip().split(' ')))
lst.sort()
f = 0
m = 100
if n == 1:
	print(0)
else:
	for i in range(n - 1):
		f = 0
		for j in range(i + 1, n):
			if lst[j] - lst[i] > k:
				f = 1
				break
		if f == 0:
			temp = i
		else:
			temp = n - j + i
		if temp < m:
			m = temp
	print(m)


a = input().split()
a[0] = int(a[0])
a[1] = int(a[1])
b = input().split()
counter = 0
maxLen = 0
for i in range(len(b)):
	b[i] = int(b[i])
b.sort()
for i in range(0, len(b)):
	for j in range(i, len(b)):
		if abs(b[i] - b[j]) <= a[1]:
			if abs(j - i) == 0 and i == j and (maxLen == 0):
				maxLen = 1
			elif abs(j - i) + 1 > maxLen:
				maxLen = abs(j - i) + 1
print(len(b) - maxLen)


(n, d) = list(map(int, input().split()))
p = list(map(int, input().split()))
m = max(p)
A = [0] * m
for pp in p:
	A[pp - 1] = A[pp - 1] + 1
minr = 1001
for i in range(m):
	x = sum(A[i:i + d + 1])
	if minr > n - x:
		minr = n - x
print(minr)


(a, b) = map(int, input().split())
z = 0
r = sorted(map(int, input().split()))
for i in range(a):
	j = 0
	for j in range(i, a):
		if r[j] - r[i] > b:
			z = max(z, j - i)
			break
	else:
		z = max(z, j - i + 1)
print(a - z)


(n, d) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
best = 100000
for i in range(len(a)):
	for j in range(i, len(a)):
		if a[j] - a[i] <= d and n - j + i - 1 < best:
			best = n - j + i - 1
print(best)


(n, d) = map(int, input().split())
mas = list(map(int, input().split()))
mas.sort()
mas.reverse()
fas = []
for a in range(n):
	for b in range(a, n):
		if mas[a] - mas[b] <= d:
			fas.append(a + n - b - 1)
if len(fas) == 0:
	print(0)
else:
	print(min(fas))


(n, d) = list(map(int, input().split()))
arr = list(map(int, input().split()))
arr.sort()
ans = n
l = 0
for r in range(n):
	while arr[r] - arr[l] > d and l < r:
		l += 1
	ans = min(ans, n - (r - l + 1))
print(ans)


(n, d) = list(map(int, input().split()))
x = list(map(int, input().split()))
x.sort()
j = 0
ans = 0
for i in range(n):
	while j < n and x[j] - x[i] <= d:
		j += 1
	if j == n or x[j] - x[i] > d:
		j -= 1
	ans = max(ans, j - i + 1)
print(n - ans)


GI = lambda : int(input())
GIS = lambda : map(int, input().split())
LGIS = lambda : list(GIS())

def main():
	(n, d) = GIS()
	ps = LGIS()
	ps.sort()
	m = {}

	def recurse(l, r):
		if (l, r) in m:
			return m[l, r]
		if ps[r] - ps[l] <= d:
			return 0
		res = 1 + min(recurse(l + 1, r), recurse(l, r - 1))
		m[l, r] = res
		return res
	print(recurse(0, n - 1))
main()


f = input()
(n, d) = f.split()
(n, d) = (int(n), int(d))
f = input()
a = f.split()
a = [int(k) for k in a]
ans = 0
count = 0
for i in range(len(a)):
	count = 0
	for j in range(len(a)):
		if a[i] <= a[j] <= a[i] + d:
			count += 1
	if count > ans:
		ans = count
print(len(a) - ans)


(n, d) = input().split()
d = int(d)
L = input().split()
for i in range(len(L)):
	L[i] = int(L[i])
L = sorted(L)
r = 1000000
for i in range(len(L)):
	for j in range(i, len(L)):
		if L[j] - L[i] <= d:
			if len(L) - len(L[i:j]) - 1 < r:
				r = len(L) - len(L[i:j]) - 1
print(r)


(n, d) = map(int, input().split())
a = sorted(list(map(int, input().split())))
ans = n - 1
for i in range(len(a)):
	j = i
	while j < len(a) and a[j] - a[i] <= d:
		j += 1
	ans = min(ans, n - (j - i))
print(ans)


class POAL:

	def main(self):
		(self.num, self.diameter) = map(int, input().strip().split(' '))
		self.inp = [int(x) for x in input().split()]
		self.inp.sort()
		self.temp = 0
		for i in range(self.num):
			self.count = 0
			for j in range(i + 1, self.num):
				if self.inp[j] - self.inp[i] <= self.diameter:
					self.count = self.count + 1
			if self.temp < self.count:
				self.temp = self.count
		print(str(self.num - self.temp - 1))
p = POAL()
p.main()


import sys
n_and_d = sys.stdin.readline()
tmp = n_and_d.split(' ')
n = int(tmp[0])
d = int(tmp[1])
l = sys.stdin.readline().strip().split(' ')
l = [int(l[i]) for i in range(0, n)]
l.sort()
min = n
for i in range(0, n):
	upper_bound_value = l[i] + d
	upper_bound_index = i
	while upper_bound_index + 1 < n and l[upper_bound_index + 1] <= upper_bound_value:
		upper_bound_index += 1
	tmp = n - 1 - upper_bound_index + i
	if tmp < min:
		min = tmp
print(min)


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

def find_upper(arr, lower, d):
	upper = lower
	for u in range(lower, len(arr)):
		if arr[u] - arr[lower] <= d:
			upper = u
	return upper
max_range = 0
for j in range(n):
	this_upper = find_upper(arr, j, d) - j + 1
	max_range = max(max_range, this_upper)
print(n - max_range)


d = int(input().split()[1])
a = sorted(map(int, input().split()))
k = i = len(a)
o = lambda x: x[-1] - x[0]
while min(list(map(o, [[j for j in a[l:l + i]] for l in range(k - i + 1)]))) > d:
	i -= 1
print(k - i)


inp = lambda : map(int, input().split())
(n, m) = inp()
a = [*inp()]
print(min([sum([0 if 0 <= i - j <= m else 1 for j in a]) for i in a]))


(n, d) = input().split()
n = int(n)
d = int(d)
x = input().split()
ans = n
for i in range(n):
	x[i] = int(x[i])
x.sort()
for i in range(n):
	for j in range(i, n):
		if x[j] - x[i] <= d:
			ans = min(ans, n - j + i - 1)
if n == 1:
	ans = 0
print(ans)


(n, d) = [int(k) for k in input().split(' ')]
arr = sorted([int(k) for k in input().split(' ')])
gmin = 9999
for i in range(len(arr)):
	j = 0
	for j in range(i, len(arr)):
		if arr[j] - arr[i] > d:
			j = j - 1
			break
	if len(arr) - j + i - 1 < gmin:
		gmin = len(arr) - j + i - 1
print(gmin)


(n, k) = map(int, input().split())
a = [0] * 101
m = 0
for i in map(int, input().split()):
	a[i] += 1
for i in range(1, 100 - k + 1):
	m = max(sum(a[i:i + k + 1]), m)
print(m if m == 0 else n - m)


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
m = -1
for i in range(n):
	for j in range(i, n):
		if a[j] - a[i] <= d and m < j - i + 1:
			m = j - i + 1
print(n - m)


ans = []
(n, x) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
for i in range(n):
	for j in range(i, n):
		if arr[j] - arr[i] <= x:
			ans.append(j - i)
if len(ans) == 0:
	print(0)
elif n == 1:
	print(0)
else:
	print(n - max(ans) - 1)


(n, d) = map(int, input().split())
a = [int(x) for x in input().split()]
a.sort()
l = 0
r = n - 1
mn = n
for i in range(n):
	l = i
	r = n
	c = a[i] + d
	while r - l > 1:
		mid = (r + l) // 2
		if a[mid] > c:
			r = mid
		else:
			l = mid
	mn = min(mn, n - (l - i + 1))
print(mn)


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
lst = []
a.sort()
for i in range(n - 1):
	for j in range(i + 1, n):
		if a[j] - a[i] <= d:
			lst.append(n - j + i - 1)
if len(lst) == 0 and len(a) == 1:
	print(0)
elif len(lst) == 0 and len(a) > 1:
	print(n - 1)
else:
	print(min(lst))


import bisect
line = input()
(n, d) = (int(line.strip().split()[0]), int(line.strip().split()[1]))
line = input()
nums = [int(item) for item in line.strip().split()]
nums = sorted(nums)
maxd = 0
for i in range(n):
	st = nums[i]
	end = nums[i] + d
	loc = bisect.bisect_right(nums, end)
	dd = loc - i
	maxd = max(maxd, dd)
print(n - maxd)


(n, d) = [int(y) for y in input().split()]
x = [int(y) for y in input().split()]
x.sort()
ans = 1000
ada = 0
for i in range(0, n):
	ada = 0
	for j in range(i + 1, n):
		if x[j] - x[i] > d:
			ada = 1
			ans = min(ans, n - i - (j - i) + i)
			break
	if ada == 0:
		ans = min(ans, i)
print(ans)


from sys import stdin
from collections import *

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 list(stdin.readline()[:-1])
(n, d) = arr_inp(1)
(x, ans) = (sorted(arr_inp(1)), float('inf'))
for i in range(n - 1):
	for j in range(i + 1, n):
		val = x[j] - x[i]
		if val <= d:
			ans = min(ans, n - (j - i + 1))
print(min(ans, n - 1))


(n, d) = [int(i) for i in input().split()]
lista = [int(i) for i in input().split()]
lista.sort()
if n == 1:
	print(0)
else:
	pares = []
	x = 0
	while x < n:
		y = x + 1
		while y < n:
			g = lista[y] - lista[x]
			if g <= d:
				pares.append((g, lista[y], lista[x]))
			y += 1
		x += 1
	if pares == []:
		print(n - 1)
	else:
		tamanhoMax = 0
		for upla in pares:
			tamanho = n - 1 - lista[::-1].index(upla[1]) - lista.index(upla[2]) + 1
			if tamanho > tamanhoMax:
				tamanhoMax = tamanho
		print(n - tamanhoMax)


(n, d) = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
mind = A[len(A) - 1] - A[0]
mini = n
if mind <= d:
	print(0)
else:
	cond = 0
	for i in range(0, len(A)):
		for j in range(len(A) - 1, i, -1):
			if A[j] - A[i] <= d:
				cond = 1
				minde = i + len(A) - j - 1
				if minde < mini:
					mini = minde
				break
	if cond == 1:
		print(mini)
	else:
		print(n - 1)


(n, d) = map(int, input().split())
(c, p) = ([0] * 102, [0] * 102)
for x in map(int, input().split()):
	c[x] += 1
for i in range(1, 102):
	p[i] = p[i - 1] + c[i]
print(n - max((p[i + d + 1] - p[i] for i in range(101 - d))))


(n, d) = [int(x) for x in input().split()]
x = [int(x) for x in input().split()]
x.sort()
res = len(x)
for i in range(len(x)):
	j = i
	while j < len(x) and x[j] <= x[i] + d:
		j += 1
	res = min(res, len(x) - j + i)
print(res)


(n, d) = map(int, input().split())
Ar = [int(x) for x in input().split()]
Ar.sort()
h = []
for i in range(n):
	A = Ar[i:]
	m = A[0] + d
	j = 0
	while j < len(A):
		if A[j] > m:
			A.remove(A[j])
		else:
			j += 1
	h.append(len(A))
print(n - max(h))


import sys
from math import *
mod = 1000000007

def coun(a, d):
	a.sort()
	if a[-1] - a[0] <= d:
		return True
	else:
		return False
(n, d) = map(int, sys.stdin.readline().split(' '))
a = list(map(int, input().strip().split(' ')))
a.sort()
maxc = 0
for i in range(n):
	for j in range(i, n):
		sl = a[i:j + 1]
		if coun(sl, d):
			maxc = max(maxc, j - i + 1)
print(n - maxc)


(n, d) = map(int, input().split())
s = [int(i) for i in input().split()]
s.sort()
ans = 0
for i in range(n):
	cnt = 0
	for j in range(n - 1, -1, -1):
		if s[j] - s[i] <= d:
			cnt = j - i
			break
	ans = max(cnt + 1, ans)
print(n - ans)


import sys
(n, d) = input().split(' ')
n = int(n)
d = int(d)
A = input()
A = [int(i) for i in A.split()]
if n == 1:
	print('0')
	sys.exit()
A.sort()
kapa = 1000000000
for i in range(len(A)):
	for j in range(i, len(A)):
		zeta = A[j] - A[i]
		if zeta <= d and n - (j - i + 1) < kapa:
			kapa = n - (j - i + 1)
print(kapa)


(n, d) = list(map(int, input().split()))
x = list(map(int, input().split()))
t = [0] * 102
for i in x:
	t[i] += 1
mn = n
for i in range(100):
	cnt = 0
	for j in range(i, min(101, i + d + 1)):
		cnt += t[j]
	if n - cnt < mn:
		mn = n - cnt
print(mn)


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * 101
su = []
for i in a:
	b[i] += 1
for i in range(1, 100 - d + 1):
	su.append(sum(b[i:i + d + 1]))
if len(su) == 0:
	print(0)
else:
	print(n - max(su))


read = lambda : map(int, input().split())
(n, d) = read()
x = sorted(list(read()))
p = 1
for i in range(n):
	m = 1
	for j in range(i + 1, n):
		if x[j] - x[i] > d:
			break
		m += 1
	p = max(p, m)
print(n - p)


(n, d) = [int(i) for i in input().split()]
e = [int(i) for i in input().split()]
g = []
for i in range(n):
	g.append(min(e))
	e[e.index(min(e))] = 1232345
w = 0
for i in range(n):
	c = 0
	h = 0
	t = g[i]
	for z in range(i, n):
		c = g[z]
		if c - t <= d:
			h += 1
	if w < h:
		w = h
print(n - w)


(n, d) = tuple([int(item) for item in input().split(' ')])
arr = [int(item) for item in input().split(' ')]
arr.sort()
l = 0
r = 0
minv = 1
while True:
	r = r + 1
	if r == n:
		break
	while not arr[r] - arr[l] <= d:
		l += 1
	minv = max(minv, r - l + 1)
print(n - minv)


(n, d) = map(int, input().split())
C = [int(x) for x in input().split()]
if n == 1:
	print(0)
else:
	C.sort()
	first = 0
	last = n - 1
	curr_d = C[last] - C[first]
	if curr_d <= d:
		print(0)
	else:
		cnt = float('inf')
		aux = float('inf')
		for i in range(n):
			for j in range(i + 1, n):
				if C[j] - C[i] <= d:
					aux = min(aux, n - j + i - 1)
				else:
					break
			cnt = min(cnt, aux)
		if cnt == float('inf'):
			cnt = n - 1
		print(cnt)


import sys

def minp():
	return sys.stdin.readline().strip()
r = 0
(n, d) = map(int, minp().split())
a = sorted(map(int, minp().split()))
l = 0
r = 0
b = []
while l < n:
	while r < n - 1 and a[r + 1] - a[l] <= d:
		r += 1
	b.append(r - l + 1)
	l += 1
print(n - max(b))


str1 = input()
str2 = input()
a = str1.split(' ')
b = str2.split(' ')
n = int(a[0])
d = int(a[1])
multiset = []
for i in b:
	multiset.append(int(i))
multiset.sort()
num = []
num.append(1)
for i in range(1, n):
	j = i - 1
	num.append(1)
	while j >= 0 and abs(multiset[i] - multiset[j]) <= d:
		num[i] += 1
		j -= 1
print(n - max(num))


(n, d) = (int(z) for z in input().split())
arr = [int(z) for z in input().split()]
arr.sort()
mx = -1
for i in range(n):
	for j in range(i, n):
		if arr[j] - arr[i] <= d:
			mx = max(mx, j - i + 1)
print(n - mx)


(n, d) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
c = [0 for i in range(102)]
for i in a:
	c[i] += 1
sum1 = [0 for i in range(500)]
for i in range(1, 101):
	sum1[i] = sum(c[i - 1:i + d])
print(n - max(sum1))


import sys

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

def read_ints():
	return [int(x) for x in input().split()]
(n, d) = read_ints()
a = read_ints()
a = sorted(a)
best = 0
for i in range(n):
	for j in range(i, n):
		if a[j] - a[i] <= d:
			best = max(best, j - i + 1)
print(len(a) - best)


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
l = 0
r = 0
ans = 0
while r < n:
	if a[r] - a[l] <= d:
		ans = max(ans, r - l + 1)
		r += 1
	else:
		l += 1
print(n - ans)


l = input()
(n, d) = l.split()
n = int(n)
d = int(d)
l = input()
l = l.split()
for i in range(0, n):
	l[i] = int(l[i])
l.sort()
while 1:
	temp = l[0]
	cnt1 = 0
	for i in range(1, len(l)):
		if l[i] - temp > d:
			cnt1 = cnt1 + 1
	temp = l[len(l) - 1]
	cnt2 = 0
	for i in range(0, len(l) - 1):
		if temp - l[i] > d:
			cnt2 = cnt2 + 1
	if cnt1 == 0 and cnt2 == 0:
		break
	if cnt2 > cnt1:
		del l[len(l) - 1]
	else:
		del l[0]
print(n - len(l))


(n, d) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
max = 0
for i in range(len(arr)):
	count = 0
	for j in range(i, len(arr)):
		if arr[j] - arr[i] <= d:
			count += 1
	if max < count:
		max = count
print(len(arr) - max)


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
i = 0
cnt = 0
cnt1 = 0
if n == 1:
	print('0')
else:
	for i in range(n):
		cnt = 0
		for j in range(i + 1, n):
			d1 = a[j] - a[i]
			if d1 > d:
				break
			cnt += 1
		if cnt1 < cnt:
			cnt1 = cnt
	print(n - cnt1 - 1)


(n, d) = [int(k) for k in input().split(' ')]
points = [int(k) for k in input().split(' ')]

def qs(A, l, r):
	if l >= r:
		return
	p = part(A, l, r)
	qs(A, l, p - 1)
	qs(A, p + 1, r)

def part(A, l, r):
	if l == r:
		return l
	pivot = A[r]
	i = l
	for j in range(l, r):
		if A[j] < pivot:
			swap(A, j, i)
			i += 1
	swap(A, r, i)
	return i

def swap(A, i, j):
	c = A[i]
	A[i] = A[j]
	A[j] = c
qs(points, 0, n - 1)
(i, j) = (0, 0)
max_dist = 0
while j < n:
	while points[j] - points[i] <= d:
		j += 1
		if j >= n:
			break
	dist = j - i
	if dist > max_dist:
		max_dist = dist
	i += 1
print(n - max_dist)


(n, d) = input().split()
(n, d) = [int(n), int(d)]
a = [int(i) for i in input().split()]
a.sort()
m = 0
for i in range(0, n):
	for j in range(i, n):
		if a[j] - a[i] <= d and j - i + 1 > m:
			m = j - i + 1
if n == 1:
	print('0')
else:
	print(n - m)


(n, d) = map(int, input().split(' '))
arr = list(map(int, input().split(' ')))
arr = sorted(arr)
break_flag = False
ans = 1000000000.0
for i in range(0, n):
	for j in reversed(range(i, n)):
		currentDim = arr[j] - arr[i]
		if currentDim <= d:
			ans = min(ans, n - (j - i + 1))
print(ans)


(n, d) = map(int, input().split())
points = list(map(int, input().split()))
points.sort()
ans = n
for i in range(n):
	j = i
	while j < n and points[j] - points[i] <= d:
		j += 1
	ans = min(ans, n - (j - i))
print(ans)


(n, d) = map(int, input().split())
a = sorted(list(map(int, input().split())))
(l, r) = (0, 0)
res = n - 1
while l < n:
	while r < n and a[r] - a[l] <= d:
		r += 1
	res = min(res, n - (r - l))
	l += 1
print(res)


(n, d) = map(int, input().split())
x = list(map(int, input().split()))
if n == 1:
	print(0)
else:
	x.sort()
	c = 0
	for i in range(n):
		for j in range(i, n):
			if x[j] - x[i] <= d and j - i + 1 > c:
				c = j - i + 1
	print(n - c)


PierwszaLinia = input().split(' ')
DrugaLinia = input().split(' ')
N = int(PierwszaLinia[0])
D = int(PierwszaLinia[1])
TablicaLiczb = []
for i in range(N):
	TablicaLiczb.append(int(DrugaLinia[i]))
TablicaLiczb.sort()
Poczatek = Koniec = Maximum = Tymczasowa = 0
Minimum = len(TablicaLiczb)
for i in range(len(TablicaLiczb)):
	while TablicaLiczb[i] - TablicaLiczb[Poczatek] > D:
		Poczatek += 1
	Tymczasowa = i - Poczatek
	if Tymczasowa > Maximum:
		Maximum = Tymczasowa
Minimum = len(TablicaLiczb) - Maximum - 1
print(Minimum)


(n, d) = map(int, input().split())
p = list(map(int, input().split()))
res = n - 1
p.sort()
for i in range(n):
	for j in range(i, n):
		if p[j] - p[i] > d:
			continue
		res = min(res, n - (j - i + 1))
print(res)


import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
(N, D) = map(int, input().split())
X = list(map(int, input().split()))
c = Counter(X)
pos = sorted(list(set(X)))
ans = 1000000000.0
for i in range(len(pos)):
	for j in range(i, len(pos)):
		xi = pos[i]
		yi = pos[j]
		d = yi - xi
		if d <= D:
			men_num = 0
			for k in range(i, j + 1):
				men_num += c[pos[k]]
			ans = min(ans, N - men_num)
print(ans)


(n, d) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
arr = sorted(arr)
res = n
l = 0
r = 0
for i in range(n):
	for j in range(i, n):
		if arr[j] - arr[i] <= d:
			res = min(res, i + (n - j) - 1)
print(res)


(n, d) = map(int, input().split())
l = [int(x) for x in input().split()]
l.sort()
ans = 10 ** 8
for i in range(n):
	for j in range(i + 1, n + 1):
		if j == n or l[j] - l[i] > d:
			ans = min(ans, n - (j - i))
			break
print(ans)


(n, d) = (int(x) for x in input().split())
ps = sorted([int(x) for x in input().split()])
r = 1000
for st in range(1, 110):
	fn = st + d
	rr = len([x for x in ps if x < st or x > fn])
	if rr < r:
		r = rr
print(r)


import os
import sys
from io import BytesIO, IOBase

def main():
	(n, d) = map(int, input().split(' '))
	a = sorted(list(map(int, input().split(' '))))
	ans = n - 1
	for x in range(n):
		for y in range(x + 1, n):
			if a[y] - a[x] <= d:
				ans = min(ans, n - y - 1 + x)
	print(ans)
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()