Hackerland is a one-dimensional city with houses aligned at integral locations along a road. The Mayor wants to install radio transmitters on the roofs of the city's houses. Each transmitter has a fixed range meaning it can transmit a signal to all houses within that number of units distance away.

Given a map of Hackerland and the transmission range, determine the minimum number of transmitters so that every house is within range of at least one transmitter.  Each transmitter must be installed on top of an existing house.

Example   

$x=[1,2,3,5,9]$ 

$k=1$    

$3$ antennae at houses $2$ and $5$ and $\mbox{9}$ provide complete coverage.  There is no house at location $7$ to cover both $5$ and $\mbox{9}$.  Ranges of coverage, are $[1,2,3]$, $\left[5\right]$, and $\left[9\right]$. 

Function Description  

Complete the hackerlandRadioTransmitters function in the editor below.   

hackerlandRadioTransmitters has the following parameter(s):  

int x[n]: the locations of houses  
int k: the effective range of a transmitter   

Returns   

int:  the minimum number of transmitters to install

Input Format

The first line contains two space-separated integers $n$ and $\boldsymbol{\mbox{k}}$, the number of houses in Hackerland and the range of each transmitter. 

The second line contains $n$ space-separated integers describing the respective locations of each house $x[i]$.

Constraints

$1\leq n,k\leq10^5$ 
$1\leq x[i]\leq10^5$
There may be more than one house at the same location.

Subtasks

$1\leq n\leq1000$ for $50\%$ of the maximum score. 

Output Format

Print a single integer denoting the minimum number of transmitters needed to cover all of the houses.

Sample Input 0

STDIN       Function
-----       --------
5 1         x[] size n = 5, k = 1
1 2 3 4 5   x = [1, 2, 3, 4, 5]  

Sample Output 0

2

Explanation 0

The diagram below depicts our map of Hackerland:

We can cover the entire city by installing $2$ transmitters on houses at locations $2$ and $\begin{array}{c}4\end{array}$.

Sample Input 1

8 2
7 2 4 6 5 9 12 11 

Sample Output 1

3

Explanation 1

The diagram below depicts our map of Hackerland:

We can cover the entire city by installing $3$ transmitters on houses at locations $\begin{array}{c}4\end{array}$, $\mbox{9}$, and $12$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Complete search


Solutions:
import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
s = set(x)
minx = x[0]
maxx = x[-1]
d = dict(zip(range(minx, maxx + 1), [False] * (maxx - minx + 1)))
cnt = 0
for xi in x:
	if d[xi]:
		continue
	if xi + k in s:
		cnt += 1
		for i in range(xi, xi + 2 * k + 1):
			d[i] = True
	else:
		for i in range(xi + k, xi - 1, -1):
			if i in s:
				for j in range(xi, i + k + 1):
					d[j] = True
				cnt += 1
				break
print(cnt)


(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
count = 0
length = len(x)
i = 0
while i < length:
	temp = x[i]
	while length > i and x[i] - temp <= k:
		i += 1
	head = x[i - 1]
	while length > i and x[i] - head <= k:
		i += 1
	count += 1
print(count)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
l = [int(x_temp) for x_temp in input().strip().split(' ')]
s = set(l)
l.sort()
count = 0
i = 0
while i < n:
	count += 1
	start = l[i]
	trans = start + k
	if trans not in s:
		while i < n and l[i] <= trans:
			i += 1
		i -= 1
		if i == n:
			break
		end = l[i] + k
		while i < n and l[i] <= end:
			i += 1
	else:
		end = start + 2 * k
		while i < n and l[i] <= end:
			i += 1
print(count)


(n, k) = (int(x) for x in input().split())
contents = {int(x) for x in input().split()}
i = min(contents)
limit = max(contents)
count = 0
while i <= limit:
	if i not in contents:
		i += 1
		continue
	nextStep = 0
	j = i + 1
	while j <= i + k:
		if j in contents:
			nextStep = j
		j += 1
	if nextStep == 0:
		count += 1
		i += k + 1
	else:
		count += 1
		i = nextStep + k + 1
print(count)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = sorted([int(x_temp) for x_temp in input().strip().split(' ')])
first_of_range = x[0]
current_transmitter_position = x[0]
prev = x[0]
counter = 1
for i in range(1, len(x)):
	el = x[i]
	if el - first_of_range <= k:
		current_transmitter_position = el
	if el - current_transmitter_position > k:
		counter += 1
		first_of_range = el
		current_transmitter_position = el
print(counter)


def check(a, i, k):
	r = i
	for j in range(i + 1, len(a)):
		if a[j] <= a[i] + k:
			r += 1
		else:
			break
	return r

def main():
	(n, k) = list(map(int, input().strip().split(' ')))
	x = list(map(int, input().strip().split(' ')))
	x.sort()
	r = []
	i = 0
	while i < len(x):
		t = check(x, i, k)
		r.append(x[t])
		i = check(x, t, k) + 1
	print(len(r))
main()


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
ans = 0
curp = x[0] + k
i = 0
found = None
srch = x[0] + k
while i < len(x):
	while i < len(x) - 1 and x[i + 1] <= srch:
		i += 1
	found = x[i]
	lim = found + k
	while i < len(x) - 1 and x[i + 1] <= lim:
		i += 1
	ans += 1
	i += 1
	if i < len(x):
		srch = x[i] + k
print(ans)


import sys
(n, k) = map(int, input().split())
x = list(sorted(map(int, input().split())))
print('read done', file=sys.stderr)
c = 0
p = x[0]
i = 0
while i < n:
	while i + 1 < n and x[i + 1] - p <= k:
		i += 1
	p = x[i]
	while i < n and x[i] - p <= k:
		i += 1
	if i < n:
		p = x[i]
	c += 1
print(c)


import sys
(n, k) = [int(x) for x in input().strip().split(' ')]
x = sorted([int(x_temp) for x_temp in input().strip().split(' ')])
distances = []
for i in range(len(x) - 1):
	distances.append(x[i + 1] - x[i])
antennas = 0
i = 0
try:
	while i < len(distances):
		tmp = 0
		while tmp + distances[i] <= k:
			tmp += distances[i]
			i += 1
		tmp = 0
		while tmp + distances[i] <= k:
			tmp += distances[i]
			i += 1
		antennas += 1
		i += 1
except:
	pass
print(antennas + 1)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
covered = 0
count = 0
current = 0
for i in range(n):
	if x[i] <= covered:
		continue
	else:
		dist = x[i] + k
		for j in range(i + 1, n):
			if x[j] > dist or j == n - 1:
				current = j - 1
				break
		covered = x[current] + k
		count += 1
print(count)


import sys
has = [0 for i in range(100001)]
has[100000] = 1
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
mm = max(x)
has = [0 for i in range(mm + k + 3)]
c = 0
j = 0
i = 0
for a in x:
	has[a] = 1
while i < mm + 1:
	if has[i] == 1:
		ss = i + k
		y = i
		while ss != y:
			if has[ss] == 1:
				break
			ss = ss - 1
		i = ss + k + 1
		c = c + 1
	else:
		i = i + 1
print(c)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
temp = [0] * 10 ** 6
for i in x:
	temp[i] = 1
count = 0
end = 0
for i in range(n):
	if x[i] > end + k or i == 0:
		start = x[i]
		end = start + k
		if end > x[-1]:
			count += 1
			break
		if temp[end] == 1:
			count += 1
		else:
			while end >= start:
				end -= 1
				if end == start:
					count += 1
					break
				if temp[end] == 1:
					count += 1
					break
print(count)


(n, k) = map(int, input().split())
ar = sorted(map(int, input().split()))
trees = []
l = ar[0]
for i in range(n):
	if ar[i] <= l + k:
		continue
	if ar[i - 1] <= l + k:
		trees.append(i - 1)
		r = ar[i - 1] + k
	if ar[i] <= r:
		continue
	l = ar[i]
if trees and ar[-1] - ar[trees[-1]] <= k:
	print(len(trees))
else:
	print(len(trees) + 1)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
sind = 0
tind = -10 ** 18
donet = False
stations = 1
for i in range(n):
	if x[i] > x[sind] + k and (not donet):
		tind = i - 1
		donet = True
	if donet and x[i] > x[tind] + k:
		stations += 1
		sind = i
		tind = -10 ** 18
		donet = False
print(stations)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
y = x
pt = y[0] + k
nbhd = 0
while len(y) > 0:
	if pt < 0:
		break
	if pt in y:
		nbhd += 1
		while len(y) > 0 and y[0] <= pt + k:
			y.pop(0)
		if len(y) > 0:
			pt = y[0] + k
	else:
		pt -= 1
print(nbhd)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = sorted([int(x_temp) for x_temp in input().strip().split(' ')])
result = 0
curr_index = 0
while curr_index < len(x):
	ideal = x[curr_index] + k
	for i in range(curr_index, len(x)):
		if x[i] == ideal:
			break
		elif x[i] > ideal:
			ideal = x[i - 1]
			break
		if i == len(x) - 1:
			ideal = x[-1]
			break
	result += 1
	while curr_index < len(x) and x[curr_index] <= ideal + k:
		curr_index += 1
print(result)


import sys

def findFirst(x, k, cnt):
	found = False
	total = x[0] + k
	while not found:
		if total in x:
			cnt.append(total)
			found = True
		else:
			total -= 1
	return cnt
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x = sorted(x)
cnt = []
findFirst(x, k, cnt)
for i in range(1, len(x)):
	if abs(x[i] - cnt[-1]) <= k:
		continue
	else:
		cnt = findFirst(x[i:], k, cnt)
print(len(cnt))


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
i = 0
p = 0
r = 0
while i < n and p < n:
	while i < n and x[i] - x[p] <= k:
		i += 1
	i -= 1
	p = i
	while i < n and x[i] - x[p] <= k:
		i += 1
	r += 1
	p = i
print(r)


def solve(k, x):
	n = len(x)
	towers = []
	i = 0
	edge = 0
	while i < n:
		while i < n and x[i] <= x[edge] + k:
			i += 1
		current = i - 1
		towers.append(current)
		while i < n and x[i] <= x[current] + k:
			i += 1
		edge = i
	return towers
(n, k) = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
print(len(solve(k, x)))


import sys
ag = [0 for i in range(100001)]
ag[100000] = 1
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
mm = max(x)
ag = [0 for i in range(mm + k + 3)]

class graph:
	__v = 0
	__next = list()

	def __init__(self, v):
		self.__v = v + 3
		self.__next = [[] for i in range(self.__v)]

	def addedge(self, a, b):
		self.__next[a].append(b)

	def bfs(self, a):
		k = [0 for i in range(self.__v)]
		dist = [0 for i in range(self.__v)]
		q = list()
		k[a] = 1
		q.append(a)
		while len(q):
			r = q.pop(0)
			sol.append(r)
			for x in self.__next[r]:
				if k[x] == 0:
					k[x] = 1
					dist[x] = dist[r] + 1
					q.append(x)
		return dist

	def bfs1(self, a):
		s = graph(self.__v)
		k = [0 for i in range(self.__v)]
		q = list()
		k[a] = 1
		q.append(a)
		while len(q):
			r = q.pop(0)
			sol.append(r)
			for x in self.__next[r]:
				if k[x] == 0:
					k[x] = 1
					q.append(x)
					s.addedge(r, x)
					s.addedge(x, r)
		return s

	def finddist(self, u, v):
		k = [0 for i in range(self.__v)]
		dist = [0 for i in range(self.__v)]
		q = list()
		k[u] = 1
		q.append(u)
		while len(q):
			r = q.pop(0)
			sol.append(r)
			for x in self.__next[r]:
				if k[x] == 0:
					k[x] = 1
					dist[x] = dist[r] + 1
					if x == v:
						return dist[x]
					q.append(x)
		return 0

	def printgraph(self):
		for x in self.__next:
			print(x)
		return self.__next

	def findlevel(self, xx):
		flag = 0
		c = 0
		for x in self.__next:
			for y in x:
				if y == xx:
					flag = self.__next.index(x)
					break
			if flag > 0:
				break
		for i in range(flag + 1):
			if len(self.__next[i]) > 0:
				c = c + 1
		return c
n = 0
while n:
	a = int(t[0])
	b = int(t[1])
	c = int(t[2])
	if a < b:
		(a, b) = (b, a)
	if c > a:
		print('1/1')
	elif c == a and c == b:
		print('1/2')
	elif c < b:
		num = c * c
		den = 2 * a * b
		g = gcd(num, den)
		print(num // g, end='')
		print('/', end='')
		print(den // g)
	else:
		num = 2 * b * (c - b) + b * b
		den = 2 * a * b
		g = gcd(num, den)
		print(num // g, end='')
		print('/', end='')
		print(den // g)
	n = n - 1

class Graph(object):

	def __init__(self):
		self.nodes = set()
		self.edges = defaultdict(list)
		self.distances = {}

	def add_node(self, value):
		self.nodes.add(value)

	def add_edge(self, from_node, to_node, distance):
		self.edges[from_node].append(to_node)
		self.edges[to_node].append(from_node)
		self.distances[from_node, to_node] = distance
d = 0
j = 0
i = 0
for a in x:
	ag[a] = 1
while i < mm + 1:
	if ag[i] == 1:
		ss = i + k
		y = i
		while ss != y:
			if ag[ss] == 1:
				break
			ss = ss - 1
		i = ss + k + 1
		d = d + 1
	else:
		i = i + 1
print(d)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = sorted([int(x_temp) for x_temp in input().strip().split(' ')])
cnt = 0
while x:
	cnt += 1
	last = x.pop()
	c = last
	while x and last - x[-1] <= k:
		c = x.pop()
	while x and c - x[-1] <= k:
		x.pop()
print(cnt)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = sorted([int(x_temp) for x_temp in input().strip().split(' ')])
ans = 1
l = 0
c = 0
for i in range(n):
	if x[i] - x[l] <= k:
		c = i
	elif x[i] - x[c] > k:
		ans += 1
		l = i
		c = i
print(ans)


(n, k) = map(int, input().split())
x = sorted([int(i) for i in input().split()])
(c, ans) = (0, 0)
while c < n:
	(max_pos, d) = (x[c] + k, c)
	while True:
		if d + 1 == n or x[d + 1] > max_pos:
			break
		d += 1
	ans += 1
	(max_pos, c) = (x[d] + k, d)
	while True:
		if c == n or x[c] > max_pos:
			break
		c += 1
print(ans)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x_ar = sorted([int(x) for x in input().strip().split(' ')])
first = -1
second = 0
cnt = 0
for x in x_ar:
	if x <= first:
		second = x + k
		continue
	if x <= second:
		continue
	first = x + k
	cnt += 1
print(cnt)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x = sorted(x)
ans = 0
center = -10000000
for i in range(len(x)):
	print(x[i], file=sys.stderr)
	if x[i] > center + k:
		ans += 1
		for j in range(i, n):
			if x[j] > x[i] + k:
				break
			center = x[j]
		print(x[i], center, file=sys.stderr)
print(ans)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x = sorted(list(set(x)))
taken_range = 0
needed = None
last = x[0]
res = 0
for elem in x:
	if needed is None and elem > taken_range:
		needed = elem
	if needed is not None and elem > needed + k:
		res += 1
		taken_range = last + k
		if elem <= taken_range:
			needed = None
		else:
			needed = elem
	last = elem
if needed is not None:
	res += 1
print(res)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
l = len(a)
count = 0
covered = 0
pos = 0
while pos < l:
	while pos < l and a[pos] <= covered:
		pos += 1
	if pos < l:
		count += 1
		i = pos
		while i + 1 < l and a[i + 1] - a[pos] <= k:
			i += 1
		covered = a[i] + k
print(count)


(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()

def dp(x):
	i = 0
	transmitter_count = 0
	while i < len(x):
		transmitter_count += 1
		front = x[i]
		middle = x[i]
		while i + 1 < len(x):
			if x[i + 1] > front + k:
				middle = x[i]
				break
			i += 1
		while i + 1 < len(x):
			if x[i + 1] > middle + k:
				break
			i += 1
		i += 1
	return transmitter_count
print(dp(x))


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = sorted([int(x_temp) for x_temp in input().strip().split(' ')])
count = 0
current = 0
total = len(x)
last = 0
while current < total:
	count += 1
	while current < total and x[current] - x[last] <= k:
		current += 1
	last = current - 1
	while current < total and x[current] - x[last] <= k:
		current += 1
	last = current
print(count)


debug = False

def findLastHouseBefore(houses, endVal, start):
	for i in range(start, len(houses)):
		if houses[i] > endVal:
			return i - 1
	return len(houses) - 1

def findFirstHouseAfter(houses, startVal, start):
	for i in range(start, len(houses)):
		if houses[i] > startVal:
			return i
	return -1
from random import shuffle
(n, k) = [int(x) for x in input().split()]
ns = [int(x) for x in input().split()]
shuffle(ns)
ns.sort()
if debug:
	print(ns)
total = 0
uppLimit = ns[0] + k
curHouse = 0
while 1:
	if debug:
		print('Buscar casa antes de ', uppLimit, ' a partir de ', curHouse)
	curHouse = findLastHouseBefore(ns, uppLimit, curHouse)
	if curHouse == -1:
		break
	if debug:
		print('Ubicar coso en ', ns[curHouse])
	total += 1
	uppLimit = ns[curHouse] + k
	if debug:
		print('Buscar casa no cubierta hasta ', uppLimit, ' a partir de ', curHouse)
	curHouse = findFirstHouseAfter(ns, uppLimit, curHouse)
	if debug:
		print('Primera casa no cubierta: ', ns[curHouse])
	if curHouse == -1:
		break
	uppLimit = ns[curHouse] + k
print(total)


import sys

def calc(x, n, k):
	result = 0
	start = 0
	mid = 0
	cursor = 1
	mode = 0
	while cursor < n:
		if mode == 0:
			if x[cursor] - x[start] <= k:
				cursor += 1
			else:
				mid = cursor - 1
				mode = 1
		elif mode == 1:
			if x[cursor] - x[mid] <= k:
				cursor += 1
			else:
				result += 1
				mode = 0
				start = cursor
				cursor += 1
	return result + 1
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x = sorted(x)
if n == 1:
	print(1)
else:
	print(calc(x, n, k))


(n, k) = map(int, input().split())
x = sorted(list(map(int, input().split())))
tot = 0
left = 0
right = 0
while left < n:
	med = left
	while med + 1 < n and x[left] + k >= x[med + 1]:
		med += 1
	right = med
	while right + 1 < n and x[med] + k >= x[right + 1]:
		right += 1
	tot += 1
	left = right + 1
print(tot)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
ans = 0
i = 0
while i < n:
	j = i
	while i < n and x[i] <= x[j] + k:
		i += 1
	ans += 1
	if i - j > 1:
		i -= 1
		j = i
		while i < n and x[i] <= x[j] + k:
			i += 1
print(ans)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x = sorted(x)
lastTransmitter = 0 - k - 1
neededToSatisfy = x[0]
transmitters = 0
for i in range(0, len(x)):
	if x[i] <= lastTransmitter + k:
		continue
	if neededToSatisfy < lastTransmitter:
		neededToSatisfy = x[i]
	if x[i] > neededToSatisfy + k:
		lastTransmitter = x[i - 1]
		transmitters += 1
		if x[i] > x[i - 1] + k:
			neededToSatisfy = x[i]
if x[-1] > lastTransmitter + k:
	transmitters += 1
print(transmitters)


(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
v = 2 * k
x = list(set(x))
x.sort()
total = 1
left = x[0]
middle = x[0]
l = 1
while l <= len(x) - 1:
	if x[l] - left > v:
		left = x[l]
		middle = x[l]
		total = total + 1
	elif x[l] - left <= k:
		middle = x[l]
	elif x[l] - middle > k:
		total = total + 1
		left = x[l]
		middle = x[l]
	l = l + 1
print(total)


(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x = sorted(list(set(x)))
last_uncovered = -1
covered = x[0] - 1
prev = 0
num = 0
for i in x:
	if i <= covered:
		prev = i
		continue
	if last_uncovered == -1:
		last_uncovered = i
	if last_uncovered + k < i:
		num += 1
		covered = prev + k
		if i <= covered:
			last_uncovered = -1
		else:
			last_uncovered = i
	prev = i
if x[-1] > covered:
	num += 1
print(num)


import sys
(n, k) = map(int, input().strip().split())
houses = list(map(int, input().strip().split()))
houses.sort()
res = 0
i = 0
while i < len(houses):
	not_covered = i
	while i < len(houses) and houses[i] - houses[not_covered] <= k:
		i += 1
	if i < len(houses):
		i -= 1
	res += 1
	t_house = i
	while i < len(houses) and houses[i] - houses[t_house] <= k:
		i += 1
print(res)


(n, k) = map(int, input().split())
xs = sorted(set(map(int, input().split())))
towers = 0
last = -10 ** 5
location = -10 ** 5
for x in xs:
	if x - location > k:
		towers += 1
		last = x
		location = x
	elif x - last <= k:
		location = x
print(towers)


from bisect import *
import sys

def bin_search(arr, x):
	lo = 0
	hi = len(arr)
	while lo + 1 < hi:
		mid = (lo + hi) // 2
		if arr[mid] <= x:
			lo = mid
		else:
			hi = mid
	return lo

def main():
	(n, k) = input().strip().split(' ')
	(n, k) = [int(n), int(k)]
	x = [int(x_temp) for x_temp in input().strip().split(' ')]
	x.sort()
	right = -1
	count = 0
	for house in x:
		if house > right:
			ind = bin_search(x, house + k)
			right = x[ind] + k
			count += 1
	print(count)
main()


import sys

def qs(x):
	if len(x) == 0:
		return []
	return qs([y for y in x if y < x[0]]) + [x[0]] + qs([y for y in x if y > x[0]])
(n, k) = [int(x) for x in input().strip().split(' ')]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x = qs(x)
d = x[0]
res = 0
flag = False
last = None
i = -1
while i < len(x) - 1:
	i += 1
	if flag:
		if x[i] - last > k:
			flag = False
			d = x[i]
			i -= 1
	elif x[i] - d > k:
		last = x[i - 1]
		res += 1
		flag = True
		i -= 1
if last is None:
	print(1)
else:
	if x[-1] - last > k:
		res += 1
	print(res)


(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
grid = [int(x_temp) for x_temp in input().strip().split(' ')]
gridHash = {}
grid.sort()
radios = 0
for x in grid:
	gridHash[x] = 1
for x in range(grid[-1] + 1):
	if x in gridHash:
		if gridHash[x] == 1:
			radios += 1
			for z in range(x + k, x - 1, -1):
				if z in gridHash:
					break
			for y in range(z - k, z + k + 1):
				if y in gridHash:
					gridHash[y] = 0
print(radios)


import sys
(n, k) = map(int, input().strip().split())
house_list = sorted(list(map(int, input().strip().split())))
curr_trans = None
curr_trans_next_house = house_list[0]
position = 'O'
num_trans = 0
i = 0
while i < len(house_list):
	if position == 'I':
		if abs(house_list[i] - curr_trans) > k:
			curr_trans_next_house = house_list[i]
			position = 'O'
			if i == len(house_list) - 1:
				num_trans += 1
		i += 1
	elif abs(curr_trans_next_house - house_list[i]) > k:
		curr_trans = house_list[i - 1]
		num_trans += 1
		position = 'I'
	elif i == len(house_list) - 1:
		num_trans += 1
		break
	else:
		i += 1
print(num_trans)


from collections import deque

def minimum_number_of_transmitters(n, k, data):
	houses = deque(sorted(data))
	answer = 0
	while houses:
		min_house_left = houses.popleft()
		house = min_house_left
		while houses and houses[0] <= min_house_left + k:
			house = houses.popleft()
		if houses:
			next_house = house
			while houses and houses[0] <= next_house + k:
				houses.popleft()
		answer += 1
	return answer
(n, k) = [int(_) for _ in input().split()]
data = [int(_) for _ in input().split()]
print(minimum_number_of_transmitters(n, k, data))


import sys
(n, k) = map(int, input().strip().split())
x = [int(x_temp) for x_temp in input().strip().split()]
x.sort()
count = 1
currMin = x[0]
currRadio = x[0]
i = 1
while i < n:
	while i < n and x[i] <= currMin + k:
		i += 1
	currRadio = x[i - 1]
	while i < n and x[i] <= currRadio + k:
		i += 1
	if i < n:
		currMin = x[i]
		currRadio = x[i]
		count += 1
print(count)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x = sorted(x)
mini = x[0]
maxi = x[n - 1]
covered = 0
next_house = 0
res = 0
for i in range(len(x)):
	h = x[i]
	if not h <= covered:
		curr_h = h
		j = 1
		while curr_h <= h + k and i + j <= len(x) - 1:
			curr_h = x[i + j]
			j += 1
		curr_h = x[i + j - 2]
		radio = curr_h
		covered = radio + k
		res += 1
print(res)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x = sorted(x)
i = 0
j = 0
icluh = 0
while icluh < n:
	visit = icluh
	while visit + 1 < n and x[visit + 1] <= x[icluh] + k:
		visit += 1
	i += 1
	j = visit
	while j < n and x[j] <= x[visit] + k:
		j += 1
	icluh = j
print(i)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
tran = x[0]
res = 1
left = x[0]
i = 1
while i < n:
	if x[i] - left <= k:
		i += 1
	else:
		tran = x[i - 1]
		while i < n and x[i] - tran <= k:
			i += 1
		if i == n:
			break
		left = x[i]
		tran = x[i]
		res += 1
print(res)


(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
(output, y) = (0, x[:])
while y:
	for (index, i) in enumerate(y):
		if y[0] < i - k:
			break
		temp = index
	output += 1
	upperBound = y[temp] + k
	for i in y[:]:
		if i <= upperBound:
			y.remove(i)
		else:
			break
print(output)


[numhouses, transmitter_range] = list(map(int, input().split()))
occupied = [False] * 100001
for s in input().split():
	occupied[int(s)] = True
last_receiving = -1
transmitters = 0
for i in range(100001):
	if last_receiving < i and occupied[i]:
		for j in range(min(i + transmitter_range, 100000), i - 1, -1):
			if occupied[j]:
				transmitters += 1
				last_receiving = j + transmitter_range
				break
print(transmitters)


(n, k) = map(int, input().split())
houses = list(set(map(int, input().split())))
houses.sort()
total = 0
left = -k
center = -k
for house in houses:
	if house - center > k:
		total += 1
		left = house
		center = house
	elif house - left <= k:
		center = house
print(total)


max_elements = 10 ** 5
(n, k) = map(int, input().split())
houses = [0] * max_elements
min_val = max_elements
max_val = 1
for i in map(int, input().split()):
	min_val = min(min_val, i)
	max_val = max(max_val, i)
	houses[i - 1] = 1
num_trams = 0
index = min_val - 1
while index < max_val:
	num_trams += 1
	while index < max_val and (not houses[index]):
		index += 1
	index += k
	while index < max_val and (not houses[index]):
		index -= 1
	index += k + 1
print(num_trams)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
tr = []
start = None
last = None
for house in sorted(x):
	if start and house - start > k:
		tr.append(last)
		start = None
	if tr and house <= tr[-1] + k:
		continue
	if start == None:
		start = house
	last = house
if start:
	tr.append(start)
print(len(tr))


import sys
import math
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
diff = 0
count = 1
j = x[0]
for i in range(1, n):
	d = x[i] - x[i - 1]
	diff += d
	if diff <= k:
		j = x[i]
	elif x[i] - j > k:
		count += 1
		diff = 0
print(count)


import sys

class BreakIt(Exception):
	pass
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x = sorted(x)
count = 0
start = x[0]
i = 0
try:
	while i < len(x):
		if x[i] < start + k:
			pass
		elif x[i] == start + k:
			count += 1
			while i < len(x):
				if not x[i] <= start + k + k:
					break
				i += 1
			if i < len(x):
				start = x[i]
			else:
				raise BreakIt
		elif x[i - 1] < start + k:
			count += 1
			temp = x[i - 1]
			while i < len(x):
				if not x[i] <= temp + k:
					break
				i += 1
			if i < len(x):
				start = x[i]
		i += 1
except BreakIt:
	pass
if start + k > max(x):
	count += 1
print(count)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = sorted([int(x_temp) for x_temp in input().strip().split(' ')])
low = -1
count = 0
while low < len(x) - 1:
	z = low + 1
	while z < len(x) and x[z] - x[low + 1] <= k:
		z += 1
	z -= 1
	count += 1
	old_low = low
	low = z
	while low < len(x) and x[low] - x[z] <= k:
		low += 1
	low -= 1
print(count)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = sorted([int(x_temp) for x_temp in input().strip().split(' ')])
t = 1
last_t_x = x[0]
left_x = x[0]
last_x = x[0]
for i in x[1:]:
	if last_t_x + k < i:
		t = t + 1
		left_x = i
	last_t_x = i if left_x + k >= i else last_t_x
	last_x = i
print(t)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
street = [0] * (max(x) + k + 1)
for house_number in x:
	street[house_number] = 1
radios = 0
for i in range(len(street)):
	if street[i] is 1:
		for j in reversed(range(i, i + k + 1)):
			if street[j] is 1:
				radios = radios + 1
				for m in range(j - k, j + k + 1):
					if street[m] is 1:
						street[m] = 2
print(radios)


array = [0 for i in range(100001)]
(n, k) = map(int, input().split())
lista = set(list(map(int, input().split())))
for i in lista:
	array[i] = 1
cont = 0
indice = 0
indice2 = 0
maxi = max(lista)
while True:
	while array[indice] == 0:
		indice += 1
		if indice >= maxi + 1:
			break
	indice2 = indice + k
	if indice2 >= maxi + 1:
		cont += 1
		break
	while array[indice2] != 1:
		indice2 -= 1
		if indice2 == indice:
			break
	cont += 1
	indice = indice2 + k + 1
	if indice >= maxi + 1:
		break
print(cont)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
A = [int(x_temp) for x_temp in input().strip().split(' ')]
list.sort(A)
i = 0
cont = 0
while i < n:
	x = i
	y = i + 1
	cont += 1
	while y < n and A[y] - A[x] <= k:
		y += 1
	z = y
	y -= 1
	while z < n and A[z] - A[y] <= k:
		z += 1
	i = z
print(cont)


import sys
(n, k) = list(map(int, input().strip().split(' ')))
h = list(set(list(map(int, input().strip().split(' ')))))
h.sort()
n = len(h) - 1
i = 0
c = 0
while i <= n:
	max_coverage = h[i] + k
	try:
		while h[i] <= max_coverage:
			i += 1
	except:
		c += 1
		break
	i -= 1
	c += 1
	max_coverage = h[i] + k
	try:
		while h[i] <= max_coverage:
			i += 1
	except:
		break
print(c)


(n, k) = map(int, input().strip().split())
x = sorted([int(x_temp) for x_temp in input().strip().split(' ')])
b = x[0]
a = b + k
c = b + k
contador = 0
num = []
inicios = [x[0]]
for pos in range(1, n):
	if x[pos] <= a:
		b = x[pos]
		c = b + k
	elif x[pos] > c:
		num += [b]
		inicios += [x[pos]]
		contador += 1
		b = x[pos]
		a = b + k
bolean = True
if len(num) == 0:
	bolean = False
	print(1)
elif num[-1] + k < inicios[-1]:
	contador += 1
if bolean:
	print(contador)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
res = 0
(left_bound, right_bound) = (-1, -1)
for i in range(len(x)):
	if right_bound >= x[i]:
		continue
	if left_bound == -1:
		left_bound = x[i]
	if i < len(x) - 1 and x[i + 1] - left_bound <= k:
		continue
	res += 1
	right_bound = x[i] + k
	left_bound = -1
print(res)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
count = 0
minNotCovered = -1
maximum = -(2 * k)
x = sorted(x)
for i in range(len(x)):
	n = -1 if i == len(x) - 1 else x[i + 1]
	curr = x[i]
	if maximum < curr:
		if minNotCovered == -1:
			minNotCovered = curr
		if n != -1 and (minNotCovered == -1 or n - k <= minNotCovered):
			continue
		minNotCovered = -1
		maximum = curr + k
		count += 1
print(count)


import sys

def solve():
	(n, k) = input().strip().split(' ')
	(n, k) = [int(n), int(k)]
	x = list(set([int(x_temp) for x_temp in input().strip().split(' ')]))
	x.sort()
	n = len(x)
	if n == 1:
		return 1
	curr = 0
	count = 0
	i = 1
	while i < n:
		count += 1
		while i < n and x[curr] + k >= x[i]:
			i += 1
		curr = i - 1
		while i < n and x[curr] + k >= x[i]:
			i += 1
		curr = i
	return count
print(solve())


import sys
sys.setrecursionlimit(20000)

def findmin(li, s, k):
	if s > len(li):
		return 0
	mi = li[s]
	lo = s
	for i in range(s + 1, len(li)):
		if li[i] <= k + mi:
			lo = i
		else:
			break
	ne = lo
	if li[lo] + k >= li[-1]:
		return 1
	for i in range(lo + 1, len(li)):
		if li[i] > li[lo] + k:
			ne = i
			break
	return 1 + findmin(li, ne, k)
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x = sorted(set(x))
print(findmin(x, 0, k))


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
dummy = set(x)
if len(dummy) <= 1:
	print(len(dummy))
else:
	candidates = list(dummy)
	candidates.sort()
	l2 = []
	while candidates:
		t = candidates.pop(0)
		coverage = range(t, t + 2 * k + 1)
		l = []
		l.append(t)
		if not candidates:
			l2.append(l)
			break
		while candidates:
			if candidates[0] in coverage:
				l.append(candidates.pop(0))
			else:
				gg = t + k
				if gg in l:
					l2.append(l)
					break
				else:
					tt = 0
					while tt < len(l):
						if l[tt] - l[0] > k:
							break
						tt = tt + 1
					tt = tt - 1
					if l[-1] - l[tt] <= k:
						l2.append(l)
						break
					else:
						tt2 = tt + 1
						while tt2 < len(l):
							if l[tt2] - l[tt] > k:
								break
							tt2 = tt2 + 1
						tt2 = tt2 - 1
						d1 = [a for a in l if a <= l[tt2]]
						d2 = [a for a in l if a > l[tt2]]
						l2.append(d1)
						candidates = d2 + candidates
						break
		else:
			gg = t + k
			if gg in l:
				l2.append(l)
				break
			else:
				tt = 0
				while tt < len(l):
					if l[tt] - l[0] > k:
						break
					tt = tt + 1
				tt = tt - 1
				if l[-1] - l[tt] <= k:
					l2.append(l)
					break
				else:
					tt2 = tt + 1
					while tt2 < len(l):
						if l[tt2] - l[tt] > k:
							break
						tt2 = tt2 + 1
					tt2 = tt2 - 1
					d1 = [a for a in l if a <= l[tt2]]
					d2 = [a for a in l if a > l[tt2]]
					l2.append(d1)
					candidates = d2 + candidates
	print(len(l2))


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x = sorted(x)

def find_next_point(p):
	dist = 0
	if p == n - 1:
		return p
	if x[p + 1] - x[p] > k:
		return p
	while p < n:
		if p == n - 1:
			return p
		else:
			p += 1
			dist += x[p] - x[p - 1]
			if dist > k:
				return p - 1
	return n - 1
dist = -1
count = 0
i = 0
while i < n:
	if dist < 0:
		i = find_next_point(i)
		dist = k
		count += 1
	else:
		if i == n - 1:
			break
		dist = dist - (x[i + 1] - x[i])
		i += 1
print(count)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
ix = 0
cnt = 0
lg = len(x)
while True:
	i = ix + 1
	while True:
		if 0 <= ix < lg and 0 <= i < lg:
			if x[ix] >= x[i] - k:
				i += 1
			else:
				break
		else:
			break
	i -= 1
	ix = i + 1
	cnt += 1
	while True:
		if 0 <= ix < lg and 0 <= i < lg:
			if x[ix] <= x[i] + k:
				ix += 1
			else:
				break
		else:
			break
	if ix >= lg:
		break
	i = ix
print(cnt)


import sys
import math
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
cctr = x[0]
edge = x[0]
nclusters = 1
for i in range(1, len(x)):
	if x[i] - cctr <= k and x[i] - edge <= k:
		cctr = x[i]
	elif x[i] - cctr <= k and x[i] - edge > k:
		cctr = cctr
	elif x[i] - cctr > k:
		edge = x[i]
		cctr = x[i]
		nclusters += 1
print(nclusters)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = list(sorted(set([int(x_temp) for x_temp in input().strip().split(' ')])))
n = len(x)
transmitter = 0
while x:
	current = x[0]
	j = 1
	transmitter += 1
	while j < n and current + k >= x[j]:
		j += 1
	current = x[j - 1]
	while j < n and current + k >= x[j]:
		j += 1
	n -= j
	x = x[j:]
print(transmitter)


(n, k) = [int(i) for i in input().split()]
xs = sorted([int(i) for i in input().split()])
i = 0
count = 0
while i < n:
	ant = i
	while ant < n - 1 and xs[ant + 1] - xs[i] <= k:
		ant += 1
	nextStart = ant + 1
	while nextStart < n and xs[nextStart] - xs[ant] <= k:
		nextStart += 1
	i = nextStart
	count += 1
print(count)


import sys

def count_minimum_transmitters(locations, transmitter_range):
	if len(locations) == 1:
		return 1
	locations.sort()
	locations.append(locations[-1] + transmitter_range + 1)
	transmitters = 0
	first_not_covered = locations[0]
	current = locations[0]
	prev = current
	it = 0
	last_transmitter_loc = 0
	while True:
		while True:
			if current > first_not_covered + transmitter_range:
				transmitters += 1
				last_transmitter_loc = prev
				break
			else:
				it += 1
				if it >= len(locations):
					break
			prev = current
			current = locations[it]
		while True:
			if current > last_transmitter_loc + transmitter_range:
				first_not_covered = current
				break
			else:
				it += 1
				if it >= len(locations):
					break
			current = locations[it]
		if it >= len(locations):
			break
	return transmitters

def main(sinp=sys.stdin, sout=sys.stdout):
	(n, k) = map(int, sinp.readline().split())
	locations = list(map(int, sinp.read().split()))
	sout.write(str(count_minimum_transmitters(locations, k)))
main()


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
i = 0
n = len(x)
count = 0
l_pos = 0
l_val = x[0]
fixed = False
while i < n:
	if fixed == False:
		if x[i] - l_val > k:
			pos = max(i - 1, l_pos)
			val = x[pos]
			fixed = True
			count += 1
			i += 1
		elif i + 1 < n and x[i + 1] - l_val <= k:
			i += 1
		else:
			pos = i
			val = x[i]
			fixed = True
			count += 1
			i += 1
	elif x[i] - val > k:
		l_pos = i
		l_val = x[i]
		fixed = False
	else:
		i += 1
print(count)


import sys

def find_pos(start):
	pos = start
	while pos + 1 <= n - 1 and x[pos + 1] <= x[start] + k:
		pos += 1
	return pos
(n, k) = map(int, input().split())
x = list(map(int, input().split()))
x = sorted(x)
start = 0
pos = find_pos(start)
count = 1
for (i, d) in enumerate(x):
	if abs(d - x[pos]) > k:
		start = i
		pos = find_pos(start)
		count += 1
print(count)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = list(sorted([int(x_temp) for x_temp in input().strip().split(' ')]))
i = 0
minpos = x[0]
num = 0
while i < n:
	if i == n - 1:
		num += 1
		i += 1
		break
	if x[i + 1] - k > minpos:
		maxr = x[i] + k
		num += 1
		i += 1
		while i < n:
			if x[i] > maxr:
				minpos = x[i]
				break
			i += 1
	else:
		i += 1
print(num)


import sys
from bisect import *

def index(a, x):
	i = bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	raise ValueError

def find_lt(a, x):
	i = bisect_left(a, x)
	if i:
		return a[i - 1]
	raise ValueError

def find_le(a, x):
	i = bisect_right(a, x)
	if i:
		return a[i - 1]
	raise ValueError

def find_le_idx(a, x):
	i = bisect_right(a, x)
	if i:
		return i - 1
	raise ValueError

def find_gt(a, x):
	i = bisect_right(a, x)
	if i != len(a):
		return a[i]
	raise ValueError

def find_ge(a, x):
	i = bisect_left(a, x)
	if i != len(a):
		return a[i]
	raise ValueError

def debug(*args):
	pass
(n, k) = [int(x) for x in sys.stdin.readline().split()]
xs = [int(x) for x in sys.stdin.readline().split()]
xs.sort()
debug(xs)
curr = 0
transmitters = 0
while curr < len(xs):
	transmitters += 1
	debug('covering', xs[curr], ':')
	max_tr_pos = xs[curr] + k
	tr = find_le(xs, max_tr_pos)
	debug('Place tx at', tr)
	max_range_idx = find_le_idx(xs, tr + k)
	curr = max_range_idx + 1
print(transmitters)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
ans = 0
i = 0
if n == 1:
	print('1')
else:
	cur = 0
	target = k
	ans = 0
	i = 1
	l = x[0]
	index = 0
	last = -1
	while i < n:
		temp = l
		while i < n and x[i] - temp <= target:
			index = i
			last = x[i]
			l = x[i]
			i += 1
		ans += 1
		te = l
		while i < n and x[i] <= te + k:
			index = i
			i += 1
		if i < n:
			l = x[i]
			i += 1
	print(ans + 1 if last != l else ans)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
coords = sorted([int(x_temp) for x_temp in input().strip().split(' ')])
covered = [False for x in coords]
transmitters = 0
this_house = 0
most_left_uncovered = 0
while this_house < len(covered):
	if this_house + 1 < len(covered) and coords[this_house + 1] - coords[most_left_uncovered] <= k:
		this_house += 1
		continue
	transmitters += 1
	if this_house == len(covered) - 1:
		break
	for i in range(most_left_uncovered, this_house + 1):
		covered[i] = True
	next_house = this_house + 1
	while coords[next_house] - coords[this_house] <= k:
		covered[next_house] = True
		next_house += 1
		if next_house == len(coords):
			break
	this_house = next_house
	most_left_uncovered = this_house
print(transmitters)


def get_first(optimal):
	point = len(x)
	for i in range(optimal + 1, len(x)):
		distance = x[i] - x[optimal]
		if distance > k:
			point = i
			break
	return point
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x = sorted(x)
values = []
first = 0
while first < len(x):
	optimal = first
	last = first + 1
	while 1:
		if last >= len(x):
			break
		distance = x[last] - x[first]
		if distance > k:
			break
		if distance <= k:
			optimal = last
		last += 1
	first = get_first(optimal)
	values.append(optimal)
print(len(values))


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x = sorted(x)
pos = 0
target = 0
res = 0
while pos < n:
	pt = pos
	while pt < n and x[pos] + k >= x[pt]:
		pt += 1
	pt -= 1
	target = x[pt]
	pos = pt
	res += 1
	while pos < n and x[pt] + k >= x[pos]:
		pos += 1
print(res)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
result = 0
currentIndex = 0
leftIndex = 0
while currentIndex < n:
	while currentIndex < n and x[leftIndex] + k >= x[currentIndex]:
		currentIndex += 1
	leftIndex = currentIndex - 1
	result += 1
	while currentIndex < n and x[leftIndex] + k >= x[currentIndex]:
		currentIndex += 1
	leftIndex = currentIndex
print(result)


(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()

def lightloc(arr, k):
	pos = 0
	lightlim = arr[0] + k
	while pos < len(arr) and arr[pos] <= lightlim:
		pos += 1
	lightrange = arr[pos - 1] + k
	while pos < len(arr) and arr[pos] <= lightrange:
		pos += 1
	return arr[pos:]
numLight = 0
while len(x) != 0:
	numLight += 1
	x = lightloc(x, k)
print(numLight)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
res = 0
i = 0
j = 0
while i < n:
	j = i
	while j + 1 < n and i < n and (x[j + 1] - x[i] <= k):
		j += 1
	res += 1
	while j < n and i < n and (x[i] - x[j] <= k):
		i += 1
print(res)


import sys
from bisect import bisect_left
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
a = [int(x_temp) for x_temp in input().strip().split(' ')]
a = sorted(set(a))
n = len(a)
i = 0
nb = 0
while 1:
	nb += 1
	p = bisect_left(a, a[i] + k, lo=i)
	if p == n:
		break
	if a[p] > a[i] + k:
		p -= 1
	if p == i:
		i += 1
		continue
	i = p
	p = bisect_left(a, a[i] + k, lo=i)
	if p == n:
		break
	if a[p] > a[i] + k:
		i = p
	else:
		i = p + 1
	if p < n and a[p] == a[i] + k:
		i = p + 1
print(nb)


import sys
(n, k) = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
ans = 0
i = 0
while i < n:
	ii = i
	while ii < n - 1 and x[ii + 1] - x[i] <= k:
		ii += 1
	ans += 1
	while i < n and x[i] - x[ii] <= k:
		i += 1
print(ans)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
pos = 0
last = -1
cpt = 0
while pos < len(x):
	if last >= 0 and x[pos] - x[last] <= k:
		j = last + 1
		while j < len(x) and x[j] - x[last] <= k:
			j += 1
		pos = j
	else:
		j = pos + 1
		while j < len(x) and x[j] - x[pos] <= k:
			j += 1
		cpt += 1
		pos = j - 1
		last = j - 1
print(cpt)


def findBestPoint(x, l, index):
	for i in range(index + 1, len(l)):
		if l[i] > x:
			if i == index + 1:
				return l[index]
			else:
				return l[i - 1]
	return -1
(n, k) = map(int, input().split())
x = sorted(list(set(list(map(int, input().split())))))
t = findBestPoint(x[0] + k, x, -1)
if t == -1:
	print(1)
else:
	count = 1
	for i in range(1, len(x)):
		if abs(x[i] - t) > k:
			t = findBestPoint(x[i] + k, x, i - 1)
			count += 1
			if t == -1:
				break
	print(count)


import sys
import math
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
count = 0
minb = x[0]
trans = False
prevb = x[0]
for b in x[1:]:
	if b > minb + k:
		if not trans:
			loc = prevb
			count = count + 1
			trans = True
		if b > loc + k:
			minb = b
			trans = False
	prevb = b
if not trans:
	count = count + 1
print(count)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x = sorted(x)
tmp_sum = 0
antennas = 0
lenx = len(x)
i = 0
flag = True
try:
	while i < lenx:
		tmp_sum = 0
		while tmp_sum <= k:
			flag = False
			i += 1
			tmp_sum = tmp_sum + x[i] - x[i - 1]
		tmp_sum = x[i] - x[i - 1]
		while tmp_sum <= k:
			flag = False
			i += 1
			tmp_sum = tmp_sum + x[i] - x[i - 1]
		antennas += 1
except:
	antennas += 1
print(antennas)


import sys
(_, transmitter_range) = map(int, input().strip().split(' '))
x = list(set(map(int, input().strip().split(' '))))

def calculate_required_transmitters_number(transmitter_range, houses):
	print(transmitter_range, houses, file=sys.stderr)
	transmitters_number = 0
	uncovered_houses = sorted(houses)
	while uncovered_houses:
		the_leftmost_house = uncovered_houses[0]
		transmitter_house = None
		while uncovered_houses and uncovered_houses[0] <= the_leftmost_house + transmitter_range:
			transmitter_house = uncovered_houses.pop(0)
		while uncovered_houses and uncovered_houses[0] <= transmitter_house + transmitter_range:
			uncovered_houses.pop(0)
		transmitters_number += 1
	return transmitters_number
print(calculate_required_transmitters_number(transmitter_range, x))


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

def doit():
	x.sort()
	top_covered = -float('inf')
	t_count = 0
	ptr = 0
	while ptr < len(x):
		while x[ptr] <= top_covered:
			ptr += 1
			if ptr >= len(x):
				return t_count
		t_count += 1
		uncovered = x[ptr]
		while ptr + 1 < len(x) and x[ptr + 1] - uncovered <= k:
			ptr += 1
		top_covered = x[ptr] + k
	return t_count
print(doit())


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
l = list()
l = [0 for i in range(100001)]
for i in x:
	l[i - 1] = 1
x = []
for i in range(100001):
	if l[i] == 1:
		x.append(i + 1)
start = 0
i = 0
c = 1
n = len(x)
while i < n:
	if x[i] <= x[start] + k:
		i = i + 1
		continue
	else:
		s = i - 1
		while i < n and x[s] + k >= x[i]:
			i += 1
		start = i
		if i < n:
			c += 1
print(c)


(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = sorted([int(x_temp) for x_temp in input().strip().split(' ')])
(pointer, end) = (x[0], x[-1])
transmitters = 0
pointer_changed = True
while pointer_changed:
	next_trans = pointer + k
	if next_trans > end:
		transmitters += 1
		break
	for i in x:
		if i > next_trans:
			break
		temp_next_trans = i
	next_trans = temp_next_trans
	transmitters += 1
	pointer = next_trans + k + 1
	pointer_changed = False
	for i in x:
		if i >= pointer:
			pointer = i
			x = x[x.index(pointer):]
			pointer_changed = True
			break
print(transmitters)


import sys
from bisect import bisect_right, bisect_left

def find_le(a, x):
	i = bisect_right(a, x)
	if i:
		return a[i - 1]
	raise ValueError

def find_ge(a, x):
	i = bisect_left(a, x)
	if i != len(a):
		return a[i]
	return -1
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = sorted([int(x_temp) for x_temp in input().strip().split(' ')])
ret = set()
covered = 0
for i in range(n):
	if x[i] <= covered:
		continue
	s = x[i] + k
	c = find_le(x, s)
	if c not in ret:
		ret.add(c)
		covered = c + k
print(len(ret))


(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
l = list()
l = [0 for i in range(100001)]
for i in x:
	l[i - 1] = 1
x = []
for i in range(100001):
	if l[i] == 1:
		x.append(i + 1)
start = 0
i = 0
c = 1
n = len(x)
while i < n:
	if x[i] <= x[start] + k:
		i = i + 1
		continue
	else:
		s = i - 1
		while i < n and x[s] + k >= x[i]:
			i += 1
		start = i
		if i < n:
			c += 1
print(c)


import sys
[n, k] = [int(x) for x in input().strip().split(' ')]
a = [int(x) for x in input().strip().split(' ')]
ar = [0 for x in range(200001)]
for x in range(len(a)):
	ar[a[x]] = 1
(cov, ret) = (0, 0)
for x in range(100001):
	if x <= cov or ar[x] != 1:
		continue
	else:
		for y in range(x + k, x - 1, -1):
			if ar[y] == 1:
				cov = y + k
				break
		ret += 1
print(ret)


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

def f():
	if n == 1:
		print('1')
		return
	x.sort()
	num = 0
	idx = 0
	cur = x[idx]
	idx = 1
	nxt = x[idx]
	while True:
		while nxt - cur <= k:
			if idx + 1 >= n:
				print(num + 1)
				return
			idx += 1
			nxt = x[idx]
		num += 1
		cur = x[idx - 1]
		while nxt - cur <= k:
			if idx + 1 >= n:
				print(num)
				return
			idx += 1
			nxt = x[idx]
		cur = nxt
		if idx + 1 >= n:
			print(num + 1)
			return
		idx += 1
		nxt = x[idx]
f()