solutions: ["import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\ns = set(x)\nminx = x[0]\nmaxx = x[-1]\nd = dict(zip(range(minx, maxx + 1), [False] * (maxx - minx + 1)))\ncnt = 0\nfor xi in x:\n\tif d[xi]:\n\t\tcontinue\n\tif xi + k in s:\n\t\tcnt += 1\n\t\tfor i in range(xi, xi + 2 * k + 1):\n\t\t\td[i] = True\n\telse:\n\t\tfor i in range(xi + k, xi - 1, -1):\n\t\t\tif i in s:\n\t\t\t\tfor j in range(xi, i + k + 1):\n\t\t\t\t\td[j] = True\n\t\t\t\tcnt += 1\n\t\t\t\tbreak\nprint(cnt)\n", "(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\ncount = 0\nlength = len(x)\ni = 0\nwhile i < length:\n\ttemp = x[i]\n\twhile length > i and x[i] - temp <= k:\n\t\ti += 1\n\thead = x[i - 1]\n\twhile length > i and x[i] - head <= k:\n\t\ti += 1\n\tcount += 1\nprint(count)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nl = [int(x_temp) for x_temp in input().strip().split(' ')]\ns = set(l)\nl.sort()\ncount = 0\ni = 0\nwhile i < n:\n\tcount += 1\n\tstart = l[i]\n\ttrans = start + k\n\tif trans not in s:\n\t\twhile i < n and l[i] <= trans:\n\t\t\ti += 1\n\t\ti -= 1\n\t\tif i == n:\n\t\t\tbreak\n\t\tend = l[i] + k\n\t\twhile i < n and l[i] <= end:\n\t\t\ti += 1\n\telse:\n\t\tend = start + 2 * k\n\t\twhile i < n and l[i] <= end:\n\t\t\ti += 1\nprint(count)\n", "(n, k) = (int(x) for x in input().split())\ncontents = {int(x) for x in input().split()}\ni = min(contents)\nlimit = max(contents)\ncount = 0\nwhile i <= limit:\n\tif i not in contents:\n\t\ti += 1\n\t\tcontinue\n\tnextStep = 0\n\tj = i + 1\n\twhile j <= i + k:\n\t\tif j in contents:\n\t\t\tnextStep = j\n\t\tj += 1\n\tif nextStep == 0:\n\t\tcount += 1\n\t\ti += k + 1\n\telse:\n\t\tcount += 1\n\t\ti = nextStep + k + 1\nprint(count)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = sorted([int(x_temp) for x_temp in input().strip().split(' ')])\nfirst_of_range = x[0]\ncurrent_transmitter_position = x[0]\nprev = x[0]\ncounter = 1\nfor i in range(1, len(x)):\n\tel = x[i]\n\tif el - first_of_range <= k:\n\t\tcurrent_transmitter_position = el\n\tif el - current_transmitter_position > k:\n\t\tcounter += 1\n\t\tfirst_of_range = el\n\t\tcurrent_transmitter_position = el\nprint(counter)\n", "def check(a, i, k):\n\tr = i\n\tfor j in range(i + 1, len(a)):\n\t\tif a[j] <= a[i] + k:\n\t\t\tr += 1\n\t\telse:\n\t\t\tbreak\n\treturn r\n\ndef main():\n\t(n, k) = list(map(int, input().strip().split(' ')))\n\tx = list(map(int, input().strip().split(' ')))\n\tx.sort()\n\tr = []\n\ti = 0\n\twhile i < len(x):\n\t\tt = check(x, i, k)\n\t\tr.append(x[t])\n\t\ti = check(x, t, k) + 1\n\tprint(len(r))\nmain()\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\nans = 0\ncurp = x[0] + k\ni = 0\nfound = None\nsrch = x[0] + k\nwhile i < len(x):\n\twhile i < len(x) - 1 and x[i + 1] <= srch:\n\t\ti += 1\n\tfound = x[i]\n\tlim = found + k\n\twhile i < len(x) - 1 and x[i + 1] <= lim:\n\t\ti += 1\n\tans += 1\n\ti += 1\n\tif i < len(x):\n\t\tsrch = x[i] + k\nprint(ans)\n", "import sys\n(n, k) = map(int, input().split())\nx = list(sorted(map(int, input().split())))\nprint('read done', file=sys.stderr)\nc = 0\np = x[0]\ni = 0\nwhile i < n:\n\twhile i + 1 < n and x[i + 1] - p <= k:\n\t\ti += 1\n\tp = x[i]\n\twhile i < n and x[i] - p <= k:\n\t\ti += 1\n\tif i < n:\n\t\tp = x[i]\n\tc += 1\nprint(c)\n", "import sys\n(n, k) = [int(x) for x in input().strip().split(' ')]\nx = sorted([int(x_temp) for x_temp in input().strip().split(' ')])\ndistances = []\nfor i in range(len(x) - 1):\n\tdistances.append(x[i + 1] - x[i])\nantennas = 0\ni = 0\ntry:\n\twhile i < len(distances):\n\t\ttmp = 0\n\t\twhile tmp + distances[i] <= k:\n\t\t\ttmp += distances[i]\n\t\t\ti += 1\n\t\ttmp = 0\n\t\twhile tmp + distances[i] <= k:\n\t\t\ttmp += distances[i]\n\t\t\ti += 1\n\t\tantennas += 1\n\t\ti += 1\nexcept:\n\tpass\nprint(antennas + 1)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\ncovered = 0\ncount = 0\ncurrent = 0\nfor i in range(n):\n\tif x[i] <= covered:\n\t\tcontinue\n\telse:\n\t\tdist = x[i] + k\n\t\tfor j in range(i + 1, n):\n\t\t\tif x[j] > dist or j == n - 1:\n\t\t\t\tcurrent = j - 1\n\t\t\t\tbreak\n\t\tcovered = x[current] + k\n\t\tcount += 1\nprint(count)\n", "import sys\nhas = [0 for i in range(100001)]\nhas[100000] = 1\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nmm = max(x)\nhas = [0 for i in range(mm + k + 3)]\nc = 0\nj = 0\ni = 0\nfor a in x:\n\thas[a] = 1\nwhile i < mm + 1:\n\tif has[i] == 1:\n\t\tss = i + k\n\t\ty = i\n\t\twhile ss != y:\n\t\t\tif has[ss] == 1:\n\t\t\t\tbreak\n\t\t\tss = ss - 1\n\t\ti = ss + k + 1\n\t\tc = c + 1\n\telse:\n\t\ti = i + 1\nprint(c)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\ntemp = [0] * 10 ** 6\nfor i in x:\n\ttemp[i] = 1\ncount = 0\nend = 0\nfor i in range(n):\n\tif x[i] > end + k or i == 0:\n\t\tstart = x[i]\n\t\tend = start + k\n\t\tif end > x[-1]:\n\t\t\tcount += 1\n\t\t\tbreak\n\t\tif temp[end] == 1:\n\t\t\tcount += 1\n\t\telse:\n\t\t\twhile end >= start:\n\t\t\t\tend -= 1\n\t\t\t\tif end == start:\n\t\t\t\t\tcount += 1\n\t\t\t\t\tbreak\n\t\t\t\tif temp[end] == 1:\n\t\t\t\t\tcount += 1\n\t\t\t\t\tbreak\nprint(count)\n", "(n, k) = map(int, input().split())\nar = sorted(map(int, input().split()))\ntrees = []\nl = ar[0]\nfor i in range(n):\n\tif ar[i] <= l + k:\n\t\tcontinue\n\tif ar[i - 1] <= l + k:\n\t\ttrees.append(i - 1)\n\t\tr = ar[i - 1] + k\n\tif ar[i] <= r:\n\t\tcontinue\n\tl = ar[i]\nif trees and ar[-1] - ar[trees[-1]] <= k:\n\tprint(len(trees))\nelse:\n\tprint(len(trees) + 1)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\nsind = 0\ntind = -10 ** 18\ndonet = False\nstations = 1\nfor i in range(n):\n\tif x[i] > x[sind] + k and (not donet):\n\t\ttind = i - 1\n\t\tdonet = True\n\tif donet and x[i] > x[tind] + k:\n\t\tstations += 1\n\t\tsind = i\n\t\ttind = -10 ** 18\n\t\tdonet = False\nprint(stations)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\ny = x\npt = y[0] + k\nnbhd = 0\nwhile len(y) > 0:\n\tif pt < 0:\n\t\tbreak\n\tif pt in y:\n\t\tnbhd += 1\n\t\twhile len(y) > 0 and y[0] <= pt + k:\n\t\t\ty.pop(0)\n\t\tif len(y) > 0:\n\t\t\tpt = y[0] + k\n\telse:\n\t\tpt -= 1\nprint(nbhd)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = sorted([int(x_temp) for x_temp in input().strip().split(' ')])\nresult = 0\ncurr_index = 0\nwhile curr_index < len(x):\n\tideal = x[curr_index] + k\n\tfor i in range(curr_index, len(x)):\n\t\tif x[i] == ideal:\n\t\t\tbreak\n\t\telif x[i] > ideal:\n\t\t\tideal = x[i - 1]\n\t\t\tbreak\n\t\tif i == len(x) - 1:\n\t\t\tideal = x[-1]\n\t\t\tbreak\n\tresult += 1\n\twhile curr_index < len(x) and x[curr_index] <= ideal + k:\n\t\tcurr_index += 1\nprint(result)\n", "import sys\n\ndef findFirst(x, k, cnt):\n\tfound = False\n\ttotal = x[0] + k\n\twhile not found:\n\t\tif total in x:\n\t\t\tcnt.append(total)\n\t\t\tfound = True\n\t\telse:\n\t\t\ttotal -= 1\n\treturn cnt\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx = sorted(x)\ncnt = []\nfindFirst(x, k, cnt)\nfor i in range(1, len(x)):\n\tif abs(x[i] - cnt[-1]) <= k:\n\t\tcontinue\n\telse:\n\t\tcnt = findFirst(x[i:], k, cnt)\nprint(len(cnt))\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\ni = 0\np = 0\nr = 0\nwhile i < n and p < n:\n\twhile i < n and x[i] - x[p] <= k:\n\t\ti += 1\n\ti -= 1\n\tp = i\n\twhile i < n and x[i] - x[p] <= k:\n\t\ti += 1\n\tr += 1\n\tp = i\nprint(r)\n", "def solve(k, x):\n\tn = len(x)\n\ttowers = []\n\ti = 0\n\tedge = 0\n\twhile i < n:\n\t\twhile i < n and x[i] <= x[edge] + k:\n\t\t\ti += 1\n\t\tcurrent = i - 1\n\t\ttowers.append(current)\n\t\twhile i < n and x[i] <= x[current] + k:\n\t\t\ti += 1\n\t\tedge = i\n\treturn towers\n(n, k) = map(int, input().split())\nx = list(map(int, input().split()))\nx.sort()\nprint(len(solve(k, x)))\n", "import sys\nag = [0 for i in range(100001)]\nag[100000] = 1\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nmm = max(x)\nag = [0 for i in range(mm + k + 3)]\n\nclass graph:\n\t__v = 0\n\t__next = list()\n\n\tdef __init__(self, v):\n\t\tself.__v = v + 3\n\t\tself.__next = [[] for i in range(self.__v)]\n\n\tdef addedge(self, a, b):\n\t\tself.__next[a].append(b)\n\n\tdef bfs(self, a):\n\t\tk = [0 for i in range(self.__v)]\n\t\tdist = [0 for i in range(self.__v)]\n\t\tq = list()\n\t\tk[a] = 1\n\t\tq.append(a)\n\t\twhile len(q):\n\t\t\tr = q.pop(0)\n\t\t\tsol.append(r)\n\t\t\tfor x in self.__next[r]:\n\t\t\t\tif k[x] == 0:\n\t\t\t\t\tk[x] = 1\n\t\t\t\t\tdist[x] = dist[r] + 1\n\t\t\t\t\tq.append(x)\n\t\treturn dist\n\n\tdef bfs1(self, a):\n\t\ts = graph(self.__v)\n\t\tk = [0 for i in range(self.__v)]\n\t\tq = list()\n\t\tk[a] = 1\n\t\tq.append(a)\n\t\twhile len(q):\n\t\t\tr = q.pop(0)\n\t\t\tsol.append(r)\n\t\t\tfor x in self.__next[r]:\n\t\t\t\tif k[x] == 0:\n\t\t\t\t\tk[x] = 1\n\t\t\t\t\tq.append(x)\n\t\t\t\t\ts.addedge(r, x)\n\t\t\t\t\ts.addedge(x, r)\n\t\treturn s\n\n\tdef finddist(self, u, v):\n\t\tk = [0 for i in range(self.__v)]\n\t\tdist = [0 for i in range(self.__v)]\n\t\tq = list()\n\t\tk[u] = 1\n\t\tq.append(u)\n\t\twhile len(q):\n\t\t\tr = q.pop(0)\n\t\t\tsol.append(r)\n\t\t\tfor x in self.__next[r]:\n\t\t\t\tif k[x] == 0:\n\t\t\t\t\tk[x] = 1\n\t\t\t\t\tdist[x] = dist[r] + 1\n\t\t\t\t\tif x == v:\n\t\t\t\t\t\treturn dist[x]\n\t\t\t\t\tq.append(x)\n\t\treturn 0\n\n\tdef printgraph(self):\n\t\tfor x in self.__next:\n\t\t\tprint(x)\n\t\treturn self.__next\n\n\tdef findlevel(self, xx):\n\t\tflag = 0\n\t\tc = 0\n\t\tfor x in self.__next:\n\t\t\tfor y in x:\n\t\t\t\tif y == xx:\n\t\t\t\t\tflag = self.__next.index(x)\n\t\t\t\t\tbreak\n\t\t\tif flag > 0:\n\t\t\t\tbreak\n\t\tfor i in range(flag + 1):\n\t\t\tif len(self.__next[i]) > 0:\n\t\t\t\tc = c + 1\n\t\treturn c\nn = 0\nwhile n:\n\ta = int(t[0])\n\tb = int(t[1])\n\tc = int(t[2])\n\tif a < b:\n\t\t(a, b) = (b, a)\n\tif c > a:\n\t\tprint('1/1')\n\telif c == a and c == b:\n\t\tprint('1/2')\n\telif c < b:\n\t\tnum = c * c\n\t\tden = 2 * a * b\n\t\tg = gcd(num, den)\n\t\tprint(num // g, end='')\n\t\tprint('/', end='')\n\t\tprint(den // g)\n\telse:\n\t\tnum = 2 * b * (c - b) + b * b\n\t\tden = 2 * a * b\n\t\tg = gcd(num, den)\n\t\tprint(num // g, end='')\n\t\tprint('/', end='')\n\t\tprint(den // g)\n\tn = n - 1\n\nclass Graph(object):\n\n\tdef __init__(self):\n\t\tself.nodes = set()\n\t\tself.edges = defaultdict(list)\n\t\tself.distances = {}\n\n\tdef add_node(self, value):\n\t\tself.nodes.add(value)\n\n\tdef add_edge(self, from_node, to_node, distance):\n\t\tself.edges[from_node].append(to_node)\n\t\tself.edges[to_node].append(from_node)\n\t\tself.distances[from_node, to_node] = distance\nd = 0\nj = 0\ni = 0\nfor a in x:\n\tag[a] = 1\nwhile i < mm + 1:\n\tif ag[i] == 1:\n\t\tss = i + k\n\t\ty = i\n\t\twhile ss != y:\n\t\t\tif ag[ss] == 1:\n\t\t\t\tbreak\n\t\t\tss = ss - 1\n\t\ti = ss + k + 1\n\t\td = d + 1\n\telse:\n\t\ti = i + 1\nprint(d)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = sorted([int(x_temp) for x_temp in input().strip().split(' ')])\ncnt = 0\nwhile x:\n\tcnt += 1\n\tlast = x.pop()\n\tc = last\n\twhile x and last - x[-1] <= k:\n\t\tc = x.pop()\n\twhile x and c - x[-1] <= k:\n\t\tx.pop()\nprint(cnt)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = sorted([int(x_temp) for x_temp in input().strip().split(' ')])\nans = 1\nl = 0\nc = 0\nfor i in range(n):\n\tif x[i] - x[l] <= k:\n\t\tc = i\n\telif x[i] - x[c] > k:\n\t\tans += 1\n\t\tl = i\n\t\tc = i\nprint(ans)\n", "(n, k) = map(int, input().split())\nx = sorted([int(i) for i in input().split()])\n(c, ans) = (0, 0)\nwhile c < n:\n\t(max_pos, d) = (x[c] + k, c)\n\twhile True:\n\t\tif d + 1 == n or x[d + 1] > max_pos:\n\t\t\tbreak\n\t\td += 1\n\tans += 1\n\t(max_pos, c) = (x[d] + k, d)\n\twhile True:\n\t\tif c == n or x[c] > max_pos:\n\t\t\tbreak\n\t\tc += 1\nprint(ans)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx_ar = sorted([int(x) for x in input().strip().split(' ')])\nfirst = -1\nsecond = 0\ncnt = 0\nfor x in x_ar:\n\tif x <= first:\n\t\tsecond = x + k\n\t\tcontinue\n\tif x <= second:\n\t\tcontinue\n\tfirst = x + k\n\tcnt += 1\nprint(cnt)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx = sorted(x)\nans = 0\ncenter = -10000000\nfor i in range(len(x)):\n\tprint(x[i], file=sys.stderr)\n\tif x[i] > center + k:\n\t\tans += 1\n\t\tfor j in range(i, n):\n\t\t\tif x[j] > x[i] + k:\n\t\t\t\tbreak\n\t\t\tcenter = x[j]\n\t\tprint(x[i], center, file=sys.stderr)\nprint(ans)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx = sorted(list(set(x)))\ntaken_range = 0\nneeded = None\nlast = x[0]\nres = 0\nfor elem in x:\n\tif needed is None and elem > taken_range:\n\t\tneeded = elem\n\tif needed is not None and elem > needed + k:\n\t\tres += 1\n\t\ttaken_range = last + k\n\t\tif elem <= taken_range:\n\t\t\tneeded = None\n\t\telse:\n\t\t\tneeded = elem\n\tlast = elem\nif needed is not None:\n\tres += 1\nprint(res)\n", "(n, k) = map(int, input().split())\na = list(map(int, input().split()))\na.sort()\nl = len(a)\ncount = 0\ncovered = 0\npos = 0\nwhile pos < l:\n\twhile pos < l and a[pos] <= covered:\n\t\tpos += 1\n\tif pos < l:\n\t\tcount += 1\n\t\ti = pos\n\t\twhile i + 1 < l and a[i + 1] - a[pos] <= k:\n\t\t\ti += 1\n\t\tcovered = a[i] + k\nprint(count)\n", "(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\n\ndef dp(x):\n\ti = 0\n\ttransmitter_count = 0\n\twhile i < len(x):\n\t\ttransmitter_count += 1\n\t\tfront = x[i]\n\t\tmiddle = x[i]\n\t\twhile i + 1 < len(x):\n\t\t\tif x[i + 1] > front + k:\n\t\t\t\tmiddle = x[i]\n\t\t\t\tbreak\n\t\t\ti += 1\n\t\twhile i + 1 < len(x):\n\t\t\tif x[i + 1] > middle + k:\n\t\t\t\tbreak\n\t\t\ti += 1\n\t\ti += 1\n\treturn transmitter_count\nprint(dp(x))\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = sorted([int(x_temp) for x_temp in input().strip().split(' ')])\ncount = 0\ncurrent = 0\ntotal = len(x)\nlast = 0\nwhile current < total:\n\tcount += 1\n\twhile current < total and x[current] - x[last] <= k:\n\t\tcurrent += 1\n\tlast = current - 1\n\twhile current < total and x[current] - x[last] <= k:\n\t\tcurrent += 1\n\tlast = current\nprint(count)\n", "debug = False\n\ndef findLastHouseBefore(houses, endVal, start):\n\tfor i in range(start, len(houses)):\n\t\tif houses[i] > endVal:\n\t\t\treturn i - 1\n\treturn len(houses) - 1\n\ndef findFirstHouseAfter(houses, startVal, start):\n\tfor i in range(start, len(houses)):\n\t\tif houses[i] > startVal:\n\t\t\treturn i\n\treturn -1\nfrom random import shuffle\n(n, k) = [int(x) for x in input().split()]\nns = [int(x) for x in input().split()]\nshuffle(ns)\nns.sort()\nif debug:\n\tprint(ns)\ntotal = 0\nuppLimit = ns[0] + k\ncurHouse = 0\nwhile 1:\n\tif debug:\n\t\tprint('Buscar casa antes de ', uppLimit, ' a partir de ', curHouse)\n\tcurHouse = findLastHouseBefore(ns, uppLimit, curHouse)\n\tif curHouse == -1:\n\t\tbreak\n\tif debug:\n\t\tprint('Ubicar coso en ', ns[curHouse])\n\ttotal += 1\n\tuppLimit = ns[curHouse] + k\n\tif debug:\n\t\tprint('Buscar casa no cubierta hasta ', uppLimit, ' a partir de ', curHouse)\n\tcurHouse = findFirstHouseAfter(ns, uppLimit, curHouse)\n\tif debug:\n\t\tprint('Primera casa no cubierta: ', ns[curHouse])\n\tif curHouse == -1:\n\t\tbreak\n\tuppLimit = ns[curHouse] + k\nprint(total)\n", "import sys\n\ndef calc(x, n, k):\n\tresult = 0\n\tstart = 0\n\tmid = 0\n\tcursor = 1\n\tmode = 0\n\twhile cursor < n:\n\t\tif mode == 0:\n\t\t\tif x[cursor] - x[start] <= k:\n\t\t\t\tcursor += 1\n\t\t\telse:\n\t\t\t\tmid = cursor - 1\n\t\t\t\tmode = 1\n\t\telif mode == 1:\n\t\t\tif x[cursor] - x[mid] <= k:\n\t\t\t\tcursor += 1\n\t\t\telse:\n\t\t\t\tresult += 1\n\t\t\t\tmode = 0\n\t\t\t\tstart = cursor\n\t\t\t\tcursor += 1\n\treturn result + 1\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx = sorted(x)\nif n == 1:\n\tprint(1)\nelse:\n\tprint(calc(x, n, k))\n", "(n, k) = map(int, input().split())\nx = sorted(list(map(int, input().split())))\ntot = 0\nleft = 0\nright = 0\nwhile left < n:\n\tmed = left\n\twhile med + 1 < n and x[left] + k >= x[med + 1]:\n\t\tmed += 1\n\tright = med\n\twhile right + 1 < n and x[med] + k >= x[right + 1]:\n\t\tright += 1\n\ttot += 1\n\tleft = right + 1\nprint(tot)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\nans = 0\ni = 0\nwhile i < n:\n\tj = i\n\twhile i < n and x[i] <= x[j] + k:\n\t\ti += 1\n\tans += 1\n\tif i - j > 1:\n\t\ti -= 1\n\t\tj = i\n\t\twhile i < n and x[i] <= x[j] + k:\n\t\t\ti += 1\nprint(ans)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx = sorted(x)\nlastTransmitter = 0 - k - 1\nneededToSatisfy = x[0]\ntransmitters = 0\nfor i in range(0, len(x)):\n\tif x[i] <= lastTransmitter + k:\n\t\tcontinue\n\tif neededToSatisfy < lastTransmitter:\n\t\tneededToSatisfy = x[i]\n\tif x[i] > neededToSatisfy + k:\n\t\tlastTransmitter = x[i - 1]\n\t\ttransmitters += 1\n\t\tif x[i] > x[i - 1] + k:\n\t\t\tneededToSatisfy = x[i]\nif x[-1] > lastTransmitter + k:\n\ttransmitters += 1\nprint(transmitters)\n", "(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nv = 2 * k\nx = list(set(x))\nx.sort()\ntotal = 1\nleft = x[0]\nmiddle = x[0]\nl = 1\nwhile l <= len(x) - 1:\n\tif x[l] - left > v:\n\t\tleft = x[l]\n\t\tmiddle = x[l]\n\t\ttotal = total + 1\n\telif x[l] - left <= k:\n\t\tmiddle = x[l]\n\telif x[l] - middle > k:\n\t\ttotal = total + 1\n\t\tleft = x[l]\n\t\tmiddle = x[l]\n\tl = l + 1\nprint(total)\n", "(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx = sorted(list(set(x)))\nlast_uncovered = -1\ncovered = x[0] - 1\nprev = 0\nnum = 0\nfor i in x:\n\tif i <= covered:\n\t\tprev = i\n\t\tcontinue\n\tif last_uncovered == -1:\n\t\tlast_uncovered = i\n\tif last_uncovered + k < i:\n\t\tnum += 1\n\t\tcovered = prev + k\n\t\tif i <= covered:\n\t\t\tlast_uncovered = -1\n\t\telse:\n\t\t\tlast_uncovered = i\n\tprev = i\nif x[-1] > covered:\n\tnum += 1\nprint(num)\n", "import sys\n(n, k) = map(int, input().strip().split())\nhouses = list(map(int, input().strip().split()))\nhouses.sort()\nres = 0\ni = 0\nwhile i < len(houses):\n\tnot_covered = i\n\twhile i < len(houses) and houses[i] - houses[not_covered] <= k:\n\t\ti += 1\n\tif i < len(houses):\n\t\ti -= 1\n\tres += 1\n\tt_house = i\n\twhile i < len(houses) and houses[i] - houses[t_house] <= k:\n\t\ti += 1\nprint(res)\n", "(n, k) = map(int, input().split())\nxs = sorted(set(map(int, input().split())))\ntowers = 0\nlast = -10 ** 5\nlocation = -10 ** 5\nfor x in xs:\n\tif x - location > k:\n\t\ttowers += 1\n\t\tlast = x\n\t\tlocation = x\n\telif x - last <= k:\n\t\tlocation = x\nprint(towers)\n", "from bisect import *\nimport sys\n\ndef bin_search(arr, x):\n\tlo = 0\n\thi = len(arr)\n\twhile lo + 1 < hi:\n\t\tmid = (lo + hi) // 2\n\t\tif arr[mid] <= x:\n\t\t\tlo = mid\n\t\telse:\n\t\t\thi = mid\n\treturn lo\n\ndef main():\n\t(n, k) = input().strip().split(' ')\n\t(n, k) = [int(n), int(k)]\n\tx = [int(x_temp) for x_temp in input().strip().split(' ')]\n\tx.sort()\n\tright = -1\n\tcount = 0\n\tfor house in x:\n\t\tif house > right:\n\t\t\tind = bin_search(x, house + k)\n\t\t\tright = x[ind] + k\n\t\t\tcount += 1\n\tprint(count)\nmain()\n", "import sys\n\ndef qs(x):\n\tif len(x) == 0:\n\t\treturn []\n\treturn qs([y for y in x if y < x[0]]) + [x[0]] + qs([y for y in x if y > x[0]])\n(n, k) = [int(x) for x in input().strip().split(' ')]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx = qs(x)\nd = x[0]\nres = 0\nflag = False\nlast = None\ni = -1\nwhile i < len(x) - 1:\n\ti += 1\n\tif flag:\n\t\tif x[i] - last > k:\n\t\t\tflag = False\n\t\t\td = x[i]\n\t\t\ti -= 1\n\telif x[i] - d > k:\n\t\tlast = x[i - 1]\n\t\tres += 1\n\t\tflag = True\n\t\ti -= 1\nif last is None:\n\tprint(1)\nelse:\n\tif x[-1] - last > k:\n\t\tres += 1\n\tprint(res)\n", "(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\ngrid = [int(x_temp) for x_temp in input().strip().split(' ')]\ngridHash = {}\ngrid.sort()\nradios = 0\nfor x in grid:\n\tgridHash[x] = 1\nfor x in range(grid[-1] + 1):\n\tif x in gridHash:\n\t\tif gridHash[x] == 1:\n\t\t\tradios += 1\n\t\t\tfor z in range(x + k, x - 1, -1):\n\t\t\t\tif z in gridHash:\n\t\t\t\t\tbreak\n\t\t\tfor y in range(z - k, z + k + 1):\n\t\t\t\tif y in gridHash:\n\t\t\t\t\tgridHash[y] = 0\nprint(radios)\n", "import sys\n(n, k) = map(int, input().strip().split())\nhouse_list = sorted(list(map(int, input().strip().split())))\ncurr_trans = None\ncurr_trans_next_house = house_list[0]\nposition = 'O'\nnum_trans = 0\ni = 0\nwhile i < len(house_list):\n\tif position == 'I':\n\t\tif abs(house_list[i] - curr_trans) > k:\n\t\t\tcurr_trans_next_house = house_list[i]\n\t\t\tposition = 'O'\n\t\t\tif i == len(house_list) - 1:\n\t\t\t\tnum_trans += 1\n\t\ti += 1\n\telif abs(curr_trans_next_house - house_list[i]) > k:\n\t\tcurr_trans = house_list[i - 1]\n\t\tnum_trans += 1\n\t\tposition = 'I'\n\telif i == len(house_list) - 1:\n\t\tnum_trans += 1\n\t\tbreak\n\telse:\n\t\ti += 1\nprint(num_trans)\n", "from collections import deque\n\ndef minimum_number_of_transmitters(n, k, data):\n\thouses = deque(sorted(data))\n\tanswer = 0\n\twhile houses:\n\t\tmin_house_left = houses.popleft()\n\t\thouse = min_house_left\n\t\twhile houses and houses[0] <= min_house_left + k:\n\t\t\thouse = houses.popleft()\n\t\tif houses:\n\t\t\tnext_house = house\n\t\t\twhile houses and houses[0] <= next_house + k:\n\t\t\t\thouses.popleft()\n\t\tanswer += 1\n\treturn answer\n(n, k) = [int(_) for _ in input().split()]\ndata = [int(_) for _ in input().split()]\nprint(minimum_number_of_transmitters(n, k, data))\n", "import sys\n(n, k) = map(int, input().strip().split())\nx = [int(x_temp) for x_temp in input().strip().split()]\nx.sort()\ncount = 1\ncurrMin = x[0]\ncurrRadio = x[0]\ni = 1\nwhile i < n:\n\twhile i < n and x[i] <= currMin + k:\n\t\ti += 1\n\tcurrRadio = x[i - 1]\n\twhile i < n and x[i] <= currRadio + k:\n\t\ti += 1\n\tif i < n:\n\t\tcurrMin = x[i]\n\t\tcurrRadio = x[i]\n\t\tcount += 1\nprint(count)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx = sorted(x)\nmini = x[0]\nmaxi = x[n - 1]\ncovered = 0\nnext_house = 0\nres = 0\nfor i in range(len(x)):\n\th = x[i]\n\tif not h <= covered:\n\t\tcurr_h = h\n\t\tj = 1\n\t\twhile curr_h <= h + k and i + j <= len(x) - 1:\n\t\t\tcurr_h = x[i + j]\n\t\t\tj += 1\n\t\tcurr_h = x[i + j - 2]\n\t\tradio = curr_h\n\t\tcovered = radio + k\n\t\tres += 1\nprint(res)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx = sorted(x)\ni = 0\nj = 0\nicluh = 0\nwhile icluh < n:\n\tvisit = icluh\n\twhile visit + 1 < n and x[visit + 1] <= x[icluh] + k:\n\t\tvisit += 1\n\ti += 1\n\tj = visit\n\twhile j < n and x[j] <= x[visit] + k:\n\t\tj += 1\n\ticluh = j\nprint(i)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\ntran = x[0]\nres = 1\nleft = x[0]\ni = 1\nwhile i < n:\n\tif x[i] - left <= k:\n\t\ti += 1\n\telse:\n\t\ttran = x[i - 1]\n\t\twhile i < n and x[i] - tran <= k:\n\t\t\ti += 1\n\t\tif i == n:\n\t\t\tbreak\n\t\tleft = x[i]\n\t\ttran = x[i]\n\t\tres += 1\nprint(res)\n", "(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\n(output, y) = (0, x[:])\nwhile y:\n\tfor (index, i) in enumerate(y):\n\t\tif y[0] < i - k:\n\t\t\tbreak\n\t\ttemp = index\n\toutput += 1\n\tupperBound = y[temp] + k\n\tfor i in y[:]:\n\t\tif i <= upperBound:\n\t\t\ty.remove(i)\n\t\telse:\n\t\t\tbreak\nprint(output)\n", "[numhouses, transmitter_range] = list(map(int, input().split()))\noccupied = [False] * 100001\nfor s in input().split():\n\toccupied[int(s)] = True\nlast_receiving = -1\ntransmitters = 0\nfor i in range(100001):\n\tif last_receiving < i and occupied[i]:\n\t\tfor j in range(min(i + transmitter_range, 100000), i - 1, -1):\n\t\t\tif occupied[j]:\n\t\t\t\ttransmitters += 1\n\t\t\t\tlast_receiving = j + transmitter_range\n\t\t\t\tbreak\nprint(transmitters)\n", "(n, k) = map(int, input().split())\nhouses = list(set(map(int, input().split())))\nhouses.sort()\ntotal = 0\nleft = -k\ncenter = -k\nfor house in houses:\n\tif house - center > k:\n\t\ttotal += 1\n\t\tleft = house\n\t\tcenter = house\n\telif house - left <= k:\n\t\tcenter = house\nprint(total)\n", "max_elements = 10 ** 5\n(n, k) = map(int, input().split())\nhouses = [0] * max_elements\nmin_val = max_elements\nmax_val = 1\nfor i in map(int, input().split()):\n\tmin_val = min(min_val, i)\n\tmax_val = max(max_val, i)\n\thouses[i - 1] = 1\nnum_trams = 0\nindex = min_val - 1\nwhile index < max_val:\n\tnum_trams += 1\n\twhile index < max_val and (not houses[index]):\n\t\tindex += 1\n\tindex += k\n\twhile index < max_val and (not houses[index]):\n\t\tindex -= 1\n\tindex += k + 1\nprint(num_trams)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\ntr = []\nstart = None\nlast = None\nfor house in sorted(x):\n\tif start and house - start > k:\n\t\ttr.append(last)\n\t\tstart = None\n\tif tr and house <= tr[-1] + k:\n\t\tcontinue\n\tif start == None:\n\t\tstart = house\n\tlast = house\nif start:\n\ttr.append(start)\nprint(len(tr))\n", "import sys\nimport math\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\ndiff = 0\ncount = 1\nj = x[0]\nfor i in range(1, n):\n\td = x[i] - x[i - 1]\n\tdiff += d\n\tif diff <= k:\n\t\tj = x[i]\n\telif x[i] - j > k:\n\t\tcount += 1\n\t\tdiff = 0\nprint(count)\n", "import sys\n\nclass BreakIt(Exception):\n\tpass\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx = sorted(x)\ncount = 0\nstart = x[0]\ni = 0\ntry:\n\twhile i < len(x):\n\t\tif x[i] < start + k:\n\t\t\tpass\n\t\telif x[i] == start + k:\n\t\t\tcount += 1\n\t\t\twhile i < len(x):\n\t\t\t\tif not x[i] <= start + k + k:\n\t\t\t\t\tbreak\n\t\t\t\ti += 1\n\t\t\tif i < len(x):\n\t\t\t\tstart = x[i]\n\t\t\telse:\n\t\t\t\traise BreakIt\n\t\telif x[i - 1] < start + k:\n\t\t\tcount += 1\n\t\t\ttemp = x[i - 1]\n\t\t\twhile i < len(x):\n\t\t\t\tif not x[i] <= temp + k:\n\t\t\t\t\tbreak\n\t\t\t\ti += 1\n\t\t\tif i < len(x):\n\t\t\t\tstart = x[i]\n\t\ti += 1\nexcept BreakIt:\n\tpass\nif start + k > max(x):\n\tcount += 1\nprint(count)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = sorted([int(x_temp) for x_temp in input().strip().split(' ')])\nlow = -1\ncount = 0\nwhile low < len(x) - 1:\n\tz = low + 1\n\twhile z < len(x) and x[z] - x[low + 1] <= k:\n\t\tz += 1\n\tz -= 1\n\tcount += 1\n\told_low = low\n\tlow = z\n\twhile low < len(x) and x[low] - x[z] <= k:\n\t\tlow += 1\n\tlow -= 1\nprint(count)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = sorted([int(x_temp) for x_temp in input().strip().split(' ')])\nt = 1\nlast_t_x = x[0]\nleft_x = x[0]\nlast_x = x[0]\nfor i in x[1:]:\n\tif last_t_x + k < i:\n\t\tt = t + 1\n\t\tleft_x = i\n\tlast_t_x = i if left_x + k >= i else last_t_x\n\tlast_x = i\nprint(t)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nstreet = [0] * (max(x) + k + 1)\nfor house_number in x:\n\tstreet[house_number] = 1\nradios = 0\nfor i in range(len(street)):\n\tif street[i] is 1:\n\t\tfor j in reversed(range(i, i + k + 1)):\n\t\t\tif street[j] is 1:\n\t\t\t\tradios = radios + 1\n\t\t\t\tfor m in range(j - k, j + k + 1):\n\t\t\t\t\tif street[m] is 1:\n\t\t\t\t\t\tstreet[m] = 2\nprint(radios)\n", "array = [0 for i in range(100001)]\n(n, k) = map(int, input().split())\nlista = set(list(map(int, input().split())))\nfor i in lista:\n\tarray[i] = 1\ncont = 0\nindice = 0\nindice2 = 0\nmaxi = max(lista)\nwhile True:\n\twhile array[indice] == 0:\n\t\tindice += 1\n\t\tif indice >= maxi + 1:\n\t\t\tbreak\n\tindice2 = indice + k\n\tif indice2 >= maxi + 1:\n\t\tcont += 1\n\t\tbreak\n\twhile array[indice2] != 1:\n\t\tindice2 -= 1\n\t\tif indice2 == indice:\n\t\t\tbreak\n\tcont += 1\n\tindice = indice2 + k + 1\n\tif indice >= maxi + 1:\n\t\tbreak\nprint(cont)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nA = [int(x_temp) for x_temp in input().strip().split(' ')]\nlist.sort(A)\ni = 0\ncont = 0\nwhile i < n:\n\tx = i\n\ty = i + 1\n\tcont += 1\n\twhile y < n and A[y] - A[x] <= k:\n\t\ty += 1\n\tz = y\n\ty -= 1\n\twhile z < n and A[z] - A[y] <= k:\n\t\tz += 1\n\ti = z\nprint(cont)\n", "import sys\n(n, k) = list(map(int, input().strip().split(' ')))\nh = list(set(list(map(int, input().strip().split(' ')))))\nh.sort()\nn = len(h) - 1\ni = 0\nc = 0\nwhile i <= n:\n\tmax_coverage = h[i] + k\n\ttry:\n\t\twhile h[i] <= max_coverage:\n\t\t\ti += 1\n\texcept:\n\t\tc += 1\n\t\tbreak\n\ti -= 1\n\tc += 1\n\tmax_coverage = h[i] + k\n\ttry:\n\t\twhile h[i] <= max_coverage:\n\t\t\ti += 1\n\texcept:\n\t\tbreak\nprint(c)\n", "(n, k) = map(int, input().strip().split())\nx = sorted([int(x_temp) for x_temp in input().strip().split(' ')])\nb = x[0]\na = b + k\nc = b + k\ncontador = 0\nnum = []\ninicios = [x[0]]\nfor pos in range(1, n):\n\tif x[pos] <= a:\n\t\tb = x[pos]\n\t\tc = b + k\n\telif x[pos] > c:\n\t\tnum += [b]\n\t\tinicios += [x[pos]]\n\t\tcontador += 1\n\t\tb = x[pos]\n\t\ta = b + k\nbolean = True\nif len(num) == 0:\n\tbolean = False\n\tprint(1)\nelif num[-1] + k < inicios[-1]:\n\tcontador += 1\nif bolean:\n\tprint(contador)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\nres = 0\n(left_bound, right_bound) = (-1, -1)\nfor i in range(len(x)):\n\tif right_bound >= x[i]:\n\t\tcontinue\n\tif left_bound == -1:\n\t\tleft_bound = x[i]\n\tif i < len(x) - 1 and x[i + 1] - left_bound <= k:\n\t\tcontinue\n\tres += 1\n\tright_bound = x[i] + k\n\tleft_bound = -1\nprint(res)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\ncount = 0\nminNotCovered = -1\nmaximum = -(2 * k)\nx = sorted(x)\nfor i in range(len(x)):\n\tn = -1 if i == len(x) - 1 else x[i + 1]\n\tcurr = x[i]\n\tif maximum < curr:\n\t\tif minNotCovered == -1:\n\t\t\tminNotCovered = curr\n\t\tif n != -1 and (minNotCovered == -1 or n - k <= minNotCovered):\n\t\t\tcontinue\n\t\tminNotCovered = -1\n\t\tmaximum = curr + k\n\t\tcount += 1\nprint(count)\n", "import sys\n\ndef solve():\n\t(n, k) = input().strip().split(' ')\n\t(n, k) = [int(n), int(k)]\n\tx = list(set([int(x_temp) for x_temp in input().strip().split(' ')]))\n\tx.sort()\n\tn = len(x)\n\tif n == 1:\n\t\treturn 1\n\tcurr = 0\n\tcount = 0\n\ti = 1\n\twhile i < n:\n\t\tcount += 1\n\t\twhile i < n and x[curr] + k >= x[i]:\n\t\t\ti += 1\n\t\tcurr = i - 1\n\t\twhile i < n and x[curr] + k >= x[i]:\n\t\t\ti += 1\n\t\tcurr = i\n\treturn count\nprint(solve())\n", "import sys\nsys.setrecursionlimit(20000)\n\ndef findmin(li, s, k):\n\tif s > len(li):\n\t\treturn 0\n\tmi = li[s]\n\tlo = s\n\tfor i in range(s + 1, len(li)):\n\t\tif li[i] <= k + mi:\n\t\t\tlo = i\n\t\telse:\n\t\t\tbreak\n\tne = lo\n\tif li[lo] + k >= li[-1]:\n\t\treturn 1\n\tfor i in range(lo + 1, len(li)):\n\t\tif li[i] > li[lo] + k:\n\t\t\tne = i\n\t\t\tbreak\n\treturn 1 + findmin(li, ne, k)\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx = sorted(set(x))\nprint(findmin(x, 0, k))\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\ndummy = set(x)\nif len(dummy) <= 1:\n\tprint(len(dummy))\nelse:\n\tcandidates = list(dummy)\n\tcandidates.sort()\n\tl2 = []\n\twhile candidates:\n\t\tt = candidates.pop(0)\n\t\tcoverage = range(t, t + 2 * k + 1)\n\t\tl = []\n\t\tl.append(t)\n\t\tif not candidates:\n\t\t\tl2.append(l)\n\t\t\tbreak\n\t\twhile candidates:\n\t\t\tif candidates[0] in coverage:\n\t\t\t\tl.append(candidates.pop(0))\n\t\t\telse:\n\t\t\t\tgg = t + k\n\t\t\t\tif gg in l:\n\t\t\t\t\tl2.append(l)\n\t\t\t\t\tbreak\n\t\t\t\telse:\n\t\t\t\t\ttt = 0\n\t\t\t\t\twhile tt < len(l):\n\t\t\t\t\t\tif l[tt] - l[0] > k:\n\t\t\t\t\t\t\tbreak\n\t\t\t\t\t\ttt = tt + 1\n\t\t\t\t\ttt = tt - 1\n\t\t\t\t\tif l[-1] - l[tt] <= k:\n\t\t\t\t\t\tl2.append(l)\n\t\t\t\t\t\tbreak\n\t\t\t\t\telse:\n\t\t\t\t\t\ttt2 = tt + 1\n\t\t\t\t\t\twhile tt2 < len(l):\n\t\t\t\t\t\t\tif l[tt2] - l[tt] > k:\n\t\t\t\t\t\t\t\tbreak\n\t\t\t\t\t\t\ttt2 = tt2 + 1\n\t\t\t\t\t\ttt2 = tt2 - 1\n\t\t\t\t\t\td1 = [a for a in l if a <= l[tt2]]\n\t\t\t\t\t\td2 = [a for a in l if a > l[tt2]]\n\t\t\t\t\t\tl2.append(d1)\n\t\t\t\t\t\tcandidates = d2 + candidates\n\t\t\t\t\t\tbreak\n\t\telse:\n\t\t\tgg = t + k\n\t\t\tif gg in l:\n\t\t\t\tl2.append(l)\n\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\ttt = 0\n\t\t\t\twhile tt < len(l):\n\t\t\t\t\tif l[tt] - l[0] > k:\n\t\t\t\t\t\tbreak\n\t\t\t\t\ttt = tt + 1\n\t\t\t\ttt = tt - 1\n\t\t\t\tif l[-1] - l[tt] <= k:\n\t\t\t\t\tl2.append(l)\n\t\t\t\t\tbreak\n\t\t\t\telse:\n\t\t\t\t\ttt2 = tt + 1\n\t\t\t\t\twhile tt2 < len(l):\n\t\t\t\t\t\tif l[tt2] - l[tt] > k:\n\t\t\t\t\t\t\tbreak\n\t\t\t\t\t\ttt2 = tt2 + 1\n\t\t\t\t\ttt2 = tt2 - 1\n\t\t\t\t\td1 = [a for a in l if a <= l[tt2]]\n\t\t\t\t\td2 = [a for a in l if a > l[tt2]]\n\t\t\t\t\tl2.append(d1)\n\t\t\t\t\tcandidates = d2 + candidates\n\tprint(len(l2))\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx = sorted(x)\n\ndef find_next_point(p):\n\tdist = 0\n\tif p == n - 1:\n\t\treturn p\n\tif x[p + 1] - x[p] > k:\n\t\treturn p\n\twhile p < n:\n\t\tif p == n - 1:\n\t\t\treturn p\n\t\telse:\n\t\t\tp += 1\n\t\t\tdist += x[p] - x[p - 1]\n\t\t\tif dist > k:\n\t\t\t\treturn p - 1\n\treturn n - 1\ndist = -1\ncount = 0\ni = 0\nwhile i < n:\n\tif dist < 0:\n\t\ti = find_next_point(i)\n\t\tdist = k\n\t\tcount += 1\n\telse:\n\t\tif i == n - 1:\n\t\t\tbreak\n\t\tdist = dist - (x[i + 1] - x[i])\n\t\ti += 1\nprint(count)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\nix = 0\ncnt = 0\nlg = len(x)\nwhile True:\n\ti = ix + 1\n\twhile True:\n\t\tif 0 <= ix < lg and 0 <= i < lg:\n\t\t\tif x[ix] >= x[i] - k:\n\t\t\t\ti += 1\n\t\t\telse:\n\t\t\t\tbreak\n\t\telse:\n\t\t\tbreak\n\ti -= 1\n\tix = i + 1\n\tcnt += 1\n\twhile True:\n\t\tif 0 <= ix < lg and 0 <= i < lg:\n\t\t\tif x[ix] <= x[i] + k:\n\t\t\t\tix += 1\n\t\t\telse:\n\t\t\t\tbreak\n\t\telse:\n\t\t\tbreak\n\tif ix >= lg:\n\t\tbreak\n\ti = ix\nprint(cnt)\n", "import sys\nimport math\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\ncctr = x[0]\nedge = x[0]\nnclusters = 1\nfor i in range(1, len(x)):\n\tif x[i] - cctr <= k and x[i] - edge <= k:\n\t\tcctr = x[i]\n\telif x[i] - cctr <= k and x[i] - edge > k:\n\t\tcctr = cctr\n\telif x[i] - cctr > k:\n\t\tedge = x[i]\n\t\tcctr = x[i]\n\t\tnclusters += 1\nprint(nclusters)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = list(sorted(set([int(x_temp) for x_temp in input().strip().split(' ')])))\nn = len(x)\ntransmitter = 0\nwhile x:\n\tcurrent = x[0]\n\tj = 1\n\ttransmitter += 1\n\twhile j < n and current + k >= x[j]:\n\t\tj += 1\n\tcurrent = x[j - 1]\n\twhile j < n and current + k >= x[j]:\n\t\tj += 1\n\tn -= j\n\tx = x[j:]\nprint(transmitter)\n", "(n, k) = [int(i) for i in input().split()]\nxs = sorted([int(i) for i in input().split()])\ni = 0\ncount = 0\nwhile i < n:\n\tant = i\n\twhile ant < n - 1 and xs[ant + 1] - xs[i] <= k:\n\t\tant += 1\n\tnextStart = ant + 1\n\twhile nextStart < n and xs[nextStart] - xs[ant] <= k:\n\t\tnextStart += 1\n\ti = nextStart\n\tcount += 1\nprint(count)\n", "import sys\n\ndef count_minimum_transmitters(locations, transmitter_range):\n\tif len(locations) == 1:\n\t\treturn 1\n\tlocations.sort()\n\tlocations.append(locations[-1] + transmitter_range + 1)\n\ttransmitters = 0\n\tfirst_not_covered = locations[0]\n\tcurrent = locations[0]\n\tprev = current\n\tit = 0\n\tlast_transmitter_loc = 0\n\twhile True:\n\t\twhile True:\n\t\t\tif current > first_not_covered + transmitter_range:\n\t\t\t\ttransmitters += 1\n\t\t\t\tlast_transmitter_loc = prev\n\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\tit += 1\n\t\t\t\tif it >= len(locations):\n\t\t\t\t\tbreak\n\t\t\tprev = current\n\t\t\tcurrent = locations[it]\n\t\twhile True:\n\t\t\tif current > last_transmitter_loc + transmitter_range:\n\t\t\t\tfirst_not_covered = current\n\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\tit += 1\n\t\t\t\tif it >= len(locations):\n\t\t\t\t\tbreak\n\t\t\tcurrent = locations[it]\n\t\tif it >= len(locations):\n\t\t\tbreak\n\treturn transmitters\n\ndef main(sinp=sys.stdin, sout=sys.stdout):\n\t(n, k) = map(int, sinp.readline().split())\n\tlocations = list(map(int, sinp.read().split()))\n\tsout.write(str(count_minimum_transmitters(locations, k)))\nmain()\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\ni = 0\nn = len(x)\ncount = 0\nl_pos = 0\nl_val = x[0]\nfixed = False\nwhile i < n:\n\tif fixed == False:\n\t\tif x[i] - l_val > k:\n\t\t\tpos = max(i - 1, l_pos)\n\t\t\tval = x[pos]\n\t\t\tfixed = True\n\t\t\tcount += 1\n\t\t\ti += 1\n\t\telif i + 1 < n and x[i + 1] - l_val <= k:\n\t\t\ti += 1\n\t\telse:\n\t\t\tpos = i\n\t\t\tval = x[i]\n\t\t\tfixed = True\n\t\t\tcount += 1\n\t\t\ti += 1\n\telif x[i] - val > k:\n\t\tl_pos = i\n\t\tl_val = x[i]\n\t\tfixed = False\n\telse:\n\t\ti += 1\nprint(count)\n", "import sys\n\ndef find_pos(start):\n\tpos = start\n\twhile pos + 1 <= n - 1 and x[pos + 1] <= x[start] + k:\n\t\tpos += 1\n\treturn pos\n(n, k) = map(int, input().split())\nx = list(map(int, input().split()))\nx = sorted(x)\nstart = 0\npos = find_pos(start)\ncount = 1\nfor (i, d) in enumerate(x):\n\tif abs(d - x[pos]) > k:\n\t\tstart = i\n\t\tpos = find_pos(start)\n\t\tcount += 1\nprint(count)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = list(sorted([int(x_temp) for x_temp in input().strip().split(' ')]))\ni = 0\nminpos = x[0]\nnum = 0\nwhile i < n:\n\tif i == n - 1:\n\t\tnum += 1\n\t\ti += 1\n\t\tbreak\n\tif x[i + 1] - k > minpos:\n\t\tmaxr = x[i] + k\n\t\tnum += 1\n\t\ti += 1\n\t\twhile i < n:\n\t\t\tif x[i] > maxr:\n\t\t\t\tminpos = x[i]\n\t\t\t\tbreak\n\t\t\ti += 1\n\telse:\n\t\ti += 1\nprint(num)\n", "import sys\nfrom bisect import *\n\ndef index(a, x):\n\ti = bisect_left(a, x)\n\tif i != len(a) and a[i] == x:\n\t\treturn i\n\traise ValueError\n\ndef find_lt(a, x):\n\ti = bisect_left(a, x)\n\tif i:\n\t\treturn a[i - 1]\n\traise ValueError\n\ndef find_le(a, x):\n\ti = bisect_right(a, x)\n\tif i:\n\t\treturn a[i - 1]\n\traise ValueError\n\ndef find_le_idx(a, x):\n\ti = bisect_right(a, x)\n\tif i:\n\t\treturn i - 1\n\traise ValueError\n\ndef find_gt(a, x):\n\ti = bisect_right(a, x)\n\tif i != len(a):\n\t\treturn a[i]\n\traise ValueError\n\ndef find_ge(a, x):\n\ti = bisect_left(a, x)\n\tif i != len(a):\n\t\treturn a[i]\n\traise ValueError\n\ndef debug(*args):\n\tpass\n(n, k) = [int(x) for x in sys.stdin.readline().split()]\nxs = [int(x) for x in sys.stdin.readline().split()]\nxs.sort()\ndebug(xs)\ncurr = 0\ntransmitters = 0\nwhile curr < len(xs):\n\ttransmitters += 1\n\tdebug('covering', xs[curr], ':')\n\tmax_tr_pos = xs[curr] + k\n\ttr = find_le(xs, max_tr_pos)\n\tdebug('Place tx at', tr)\n\tmax_range_idx = find_le_idx(xs, tr + k)\n\tcurr = max_range_idx + 1\nprint(transmitters)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\nans = 0\ni = 0\nif n == 1:\n\tprint('1')\nelse:\n\tcur = 0\n\ttarget = k\n\tans = 0\n\ti = 1\n\tl = x[0]\n\tindex = 0\n\tlast = -1\n\twhile i < n:\n\t\ttemp = l\n\t\twhile i < n and x[i] - temp <= target:\n\t\t\tindex = i\n\t\t\tlast = x[i]\n\t\t\tl = x[i]\n\t\t\ti += 1\n\t\tans += 1\n\t\tte = l\n\t\twhile i < n and x[i] <= te + k:\n\t\t\tindex = i\n\t\t\ti += 1\n\t\tif i < n:\n\t\t\tl = x[i]\n\t\t\ti += 1\n\tprint(ans + 1 if last != l else ans)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\ncoords = sorted([int(x_temp) for x_temp in input().strip().split(' ')])\ncovered = [False for x in coords]\ntransmitters = 0\nthis_house = 0\nmost_left_uncovered = 0\nwhile this_house < len(covered):\n\tif this_house + 1 < len(covered) and coords[this_house + 1] - coords[most_left_uncovered] <= k:\n\t\tthis_house += 1\n\t\tcontinue\n\ttransmitters += 1\n\tif this_house == len(covered) - 1:\n\t\tbreak\n\tfor i in range(most_left_uncovered, this_house + 1):\n\t\tcovered[i] = True\n\tnext_house = this_house + 1\n\twhile coords[next_house] - coords[this_house] <= k:\n\t\tcovered[next_house] = True\n\t\tnext_house += 1\n\t\tif next_house == len(coords):\n\t\t\tbreak\n\tthis_house = next_house\n\tmost_left_uncovered = this_house\nprint(transmitters)\n", "def get_first(optimal):\n\tpoint = len(x)\n\tfor i in range(optimal + 1, len(x)):\n\t\tdistance = x[i] - x[optimal]\n\t\tif distance > k:\n\t\t\tpoint = i\n\t\t\tbreak\n\treturn point\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx = sorted(x)\nvalues = []\nfirst = 0\nwhile first < len(x):\n\toptimal = first\n\tlast = first + 1\n\twhile 1:\n\t\tif last >= len(x):\n\t\t\tbreak\n\t\tdistance = x[last] - x[first]\n\t\tif distance > k:\n\t\t\tbreak\n\t\tif distance <= k:\n\t\t\toptimal = last\n\t\tlast += 1\n\tfirst = get_first(optimal)\n\tvalues.append(optimal)\nprint(len(values))\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx = sorted(x)\npos = 0\ntarget = 0\nres = 0\nwhile pos < n:\n\tpt = pos\n\twhile pt < n and x[pos] + k >= x[pt]:\n\t\tpt += 1\n\tpt -= 1\n\ttarget = x[pt]\n\tpos = pt\n\tres += 1\n\twhile pos < n and x[pt] + k >= x[pos]:\n\t\tpos += 1\nprint(res)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\nresult = 0\ncurrentIndex = 0\nleftIndex = 0\nwhile currentIndex < n:\n\twhile currentIndex < n and x[leftIndex] + k >= x[currentIndex]:\n\t\tcurrentIndex += 1\n\tleftIndex = currentIndex - 1\n\tresult += 1\n\twhile currentIndex < n and x[leftIndex] + k >= x[currentIndex]:\n\t\tcurrentIndex += 1\n\tleftIndex = currentIndex\nprint(result)\n", "(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\n\ndef lightloc(arr, k):\n\tpos = 0\n\tlightlim = arr[0] + k\n\twhile pos < len(arr) and arr[pos] <= lightlim:\n\t\tpos += 1\n\tlightrange = arr[pos - 1] + k\n\twhile pos < len(arr) and arr[pos] <= lightrange:\n\t\tpos += 1\n\treturn arr[pos:]\nnumLight = 0\nwhile len(x) != 0:\n\tnumLight += 1\n\tx = lightloc(x, k)\nprint(numLight)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\nres = 0\ni = 0\nj = 0\nwhile i < n:\n\tj = i\n\twhile j + 1 < n and i < n and (x[j + 1] - x[i] <= k):\n\t\tj += 1\n\tres += 1\n\twhile j < n and i < n and (x[i] - x[j] <= k):\n\t\ti += 1\nprint(res)\n", "import sys\nfrom bisect import bisect_left\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\na = [int(x_temp) for x_temp in input().strip().split(' ')]\na = sorted(set(a))\nn = len(a)\ni = 0\nnb = 0\nwhile 1:\n\tnb += 1\n\tp = bisect_left(a, a[i] + k, lo=i)\n\tif p == n:\n\t\tbreak\n\tif a[p] > a[i] + k:\n\t\tp -= 1\n\tif p == i:\n\t\ti += 1\n\t\tcontinue\n\ti = p\n\tp = bisect_left(a, a[i] + k, lo=i)\n\tif p == n:\n\t\tbreak\n\tif a[p] > a[i] + k:\n\t\ti = p\n\telse:\n\t\ti = p + 1\n\tif p < n and a[p] == a[i] + k:\n\t\ti = p + 1\nprint(nb)\n", "import sys\n(n, k) = map(int, input().split())\nx = list(map(int, input().split()))\nx.sort()\nans = 0\ni = 0\nwhile i < n:\n\tii = i\n\twhile ii < n - 1 and x[ii + 1] - x[i] <= k:\n\t\tii += 1\n\tans += 1\n\twhile i < n and x[i] - x[ii] <= k:\n\t\ti += 1\nprint(ans)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\npos = 0\nlast = -1\ncpt = 0\nwhile pos < len(x):\n\tif last >= 0 and x[pos] - x[last] <= k:\n\t\tj = last + 1\n\t\twhile j < len(x) and x[j] - x[last] <= k:\n\t\t\tj += 1\n\t\tpos = j\n\telse:\n\t\tj = pos + 1\n\t\twhile j < len(x) and x[j] - x[pos] <= k:\n\t\t\tj += 1\n\t\tcpt += 1\n\t\tpos = j - 1\n\t\tlast = j - 1\nprint(cpt)\n", "def findBestPoint(x, l, index):\n\tfor i in range(index + 1, len(l)):\n\t\tif l[i] > x:\n\t\t\tif i == index + 1:\n\t\t\t\treturn l[index]\n\t\t\telse:\n\t\t\t\treturn l[i - 1]\n\treturn -1\n(n, k) = map(int, input().split())\nx = sorted(list(set(list(map(int, input().split())))))\nt = findBestPoint(x[0] + k, x, -1)\nif t == -1:\n\tprint(1)\nelse:\n\tcount = 1\n\tfor i in range(1, len(x)):\n\t\tif abs(x[i] - t) > k:\n\t\t\tt = findBestPoint(x[i] + k, x, i - 1)\n\t\t\tcount += 1\n\t\t\tif t == -1:\n\t\t\t\tbreak\n\tprint(count)\n", "import sys\nimport math\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\ncount = 0\nminb = x[0]\ntrans = False\nprevb = x[0]\nfor b in x[1:]:\n\tif b > minb + k:\n\t\tif not trans:\n\t\t\tloc = prevb\n\t\t\tcount = count + 1\n\t\t\ttrans = True\n\t\tif b > loc + k:\n\t\t\tminb = b\n\t\t\ttrans = False\n\tprevb = b\nif not trans:\n\tcount = count + 1\nprint(count)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx = sorted(x)\ntmp_sum = 0\nantennas = 0\nlenx = len(x)\ni = 0\nflag = True\ntry:\n\twhile i < lenx:\n\t\ttmp_sum = 0\n\t\twhile tmp_sum <= k:\n\t\t\tflag = False\n\t\t\ti += 1\n\t\t\ttmp_sum = tmp_sum + x[i] - x[i - 1]\n\t\ttmp_sum = x[i] - x[i - 1]\n\t\twhile tmp_sum <= k:\n\t\t\tflag = False\n\t\t\ti += 1\n\t\t\ttmp_sum = tmp_sum + x[i] - x[i - 1]\n\t\tantennas += 1\nexcept:\n\tantennas += 1\nprint(antennas)\n", "import sys\n(_, transmitter_range) = map(int, input().strip().split(' '))\nx = list(set(map(int, input().strip().split(' '))))\n\ndef calculate_required_transmitters_number(transmitter_range, houses):\n\tprint(transmitter_range, houses, file=sys.stderr)\n\ttransmitters_number = 0\n\tuncovered_houses = sorted(houses)\n\twhile uncovered_houses:\n\t\tthe_leftmost_house = uncovered_houses[0]\n\t\ttransmitter_house = None\n\t\twhile uncovered_houses and uncovered_houses[0] <= the_leftmost_house + transmitter_range:\n\t\t\ttransmitter_house = uncovered_houses.pop(0)\n\t\twhile uncovered_houses and uncovered_houses[0] <= transmitter_house + transmitter_range:\n\t\t\tuncovered_houses.pop(0)\n\t\ttransmitters_number += 1\n\treturn transmitters_number\nprint(calculate_required_transmitters_number(transmitter_range, x))\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\n\ndef doit():\n\tx.sort()\n\ttop_covered = -float('inf')\n\tt_count = 0\n\tptr = 0\n\twhile ptr < len(x):\n\t\twhile x[ptr] <= top_covered:\n\t\t\tptr += 1\n\t\t\tif ptr >= len(x):\n\t\t\t\treturn t_count\n\t\tt_count += 1\n\t\tuncovered = x[ptr]\n\t\twhile ptr + 1 < len(x) and x[ptr + 1] - uncovered <= k:\n\t\t\tptr += 1\n\t\ttop_covered = x[ptr] + k\n\treturn t_count\nprint(doit())\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\nl = list()\nl = [0 for i in range(100001)]\nfor i in x:\n\tl[i - 1] = 1\nx = []\nfor i in range(100001):\n\tif l[i] == 1:\n\t\tx.append(i + 1)\nstart = 0\ni = 0\nc = 1\nn = len(x)\nwhile i < n:\n\tif x[i] <= x[start] + k:\n\t\ti = i + 1\n\t\tcontinue\n\telse:\n\t\ts = i - 1\n\t\twhile i < n and x[s] + k >= x[i]:\n\t\t\ti += 1\n\t\tstart = i\n\t\tif i < n:\n\t\t\tc += 1\nprint(c)\n", "(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = sorted([int(x_temp) for x_temp in input().strip().split(' ')])\n(pointer, end) = (x[0], x[-1])\ntransmitters = 0\npointer_changed = True\nwhile pointer_changed:\n\tnext_trans = pointer + k\n\tif next_trans > end:\n\t\ttransmitters += 1\n\t\tbreak\n\tfor i in x:\n\t\tif i > next_trans:\n\t\t\tbreak\n\t\ttemp_next_trans = i\n\tnext_trans = temp_next_trans\n\ttransmitters += 1\n\tpointer = next_trans + k + 1\n\tpointer_changed = False\n\tfor i in x:\n\t\tif i >= pointer:\n\t\t\tpointer = i\n\t\t\tx = x[x.index(pointer):]\n\t\t\tpointer_changed = True\n\t\t\tbreak\nprint(transmitters)\n", "import sys\nfrom bisect import bisect_right, bisect_left\n\ndef find_le(a, x):\n\ti = bisect_right(a, x)\n\tif i:\n\t\treturn a[i - 1]\n\traise ValueError\n\ndef find_ge(a, x):\n\ti = bisect_left(a, x)\n\tif i != len(a):\n\t\treturn a[i]\n\treturn -1\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = sorted([int(x_temp) for x_temp in input().strip().split(' ')])\nret = set()\ncovered = 0\nfor i in range(n):\n\tif x[i] <= covered:\n\t\tcontinue\n\ts = x[i] + k\n\tc = find_le(x, s)\n\tif c not in ret:\n\t\tret.add(c)\n\t\tcovered = c + k\nprint(len(ret))\n", "(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\nx.sort()\nl = list()\nl = [0 for i in range(100001)]\nfor i in x:\n\tl[i - 1] = 1\nx = []\nfor i in range(100001):\n\tif l[i] == 1:\n\t\tx.append(i + 1)\nstart = 0\ni = 0\nc = 1\nn = len(x)\nwhile i < n:\n\tif x[i] <= x[start] + k:\n\t\ti = i + 1\n\t\tcontinue\n\telse:\n\t\ts = i - 1\n\t\twhile i < n and x[s] + k >= x[i]:\n\t\t\ti += 1\n\t\tstart = i\n\t\tif i < n:\n\t\t\tc += 1\nprint(c)\n", "import sys\n[n, k] = [int(x) for x in input().strip().split(' ')]\na = [int(x) for x in input().strip().split(' ')]\nar = [0 for x in range(200001)]\nfor x in range(len(a)):\n\tar[a[x]] = 1\n(cov, ret) = (0, 0)\nfor x in range(100001):\n\tif x <= cov or ar[x] != 1:\n\t\tcontinue\n\telse:\n\t\tfor y in range(x + k, x - 1, -1):\n\t\t\tif ar[y] == 1:\n\t\t\t\tcov = y + k\n\t\t\t\tbreak\n\t\tret += 1\nprint(ret)\n", "import sys\n(n, k) = input().strip().split(' ')\n(n, k) = [int(n), int(k)]\nx = [int(x_temp) for x_temp in input().strip().split(' ')]\n\ndef f():\n\tif n == 1:\n\t\tprint('1')\n\t\treturn\n\tx.sort()\n\tnum = 0\n\tidx = 0\n\tcur = x[idx]\n\tidx = 1\n\tnxt = x[idx]\n\twhile True:\n\t\twhile nxt - cur <= k:\n\t\t\tif idx + 1 >= n:\n\t\t\t\tprint(num + 1)\n\t\t\t\treturn\n\t\t\tidx += 1\n\t\t\tnxt = x[idx]\n\t\tnum += 1\n\t\tcur = x[idx - 1]\n\t\twhile nxt - cur <= k:\n\t\t\tif idx + 1 >= n:\n\t\t\t\tprint(num)\n\t\t\t\treturn\n\t\t\tidx += 1\n\t\t\tnxt = x[idx]\n\t\tcur = nxt\n\t\tif idx + 1 >= n:\n\t\t\tprint(num + 1)\n\t\t\treturn\n\t\tidx += 1\n\t\tnxt = x[idx]\nf()\n"]

difficulty: MEDIUM

source: hacker rank

skill_types: ['Complete search']

question:
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:

![image](1.png)

![image](2.png)
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$.

image_tags:
Linear Data Structure
Linear Data Structure

data_split: test


raw_problem:
A snowflake of order $n$ is formed by overlaying an equilateral triangle (rotated by $180$ degrees) onto each equilateral triangle of the same size in a snowflake of order $n-1$. A snowflake of order $1$ is a single equilateral triangle.

Some areas of the snowflake are overlaid repeatedly. In the above picture, blue represents the areas that are one layer thick, red two layers thick, yellow three layers thick, and so on.

For an order $n$ snowflake, let $A(n)$ be the number of triangles that are one layer thick, and let $B(n)$ be the number of triangles that are three layers thick. Define $G(n) = \gcd(A(n), B(n))$.

E.g. $A(3) = 30$, $B(3) = 6$, $G(3)=6$.

$A(11) = 3027630$, $B(11) = 19862070$, $G(11) = 30$.

Further, $G(500) = 186$ and $\sum_{n=3}^{500}G(n)=5124$.

Find $\displaystyle \sum_{n=3}^{10^7}G(n)$.

problem:
A snowflake of order $n$ is formed by overlaying an equilateral triangle (rotated by $180$ degrees) onto each equilateral triangle of the same size in a snowflake of order $n-1$. A snowflake of order $1$ is a single equilateral triangle.
 ![image](images/ep_570/1.png)
Some areas of the snowflake are overlaid repeatedly. In the above picture, blue represents the areas that are one layer thick, red two layers thick, yellow three layers thick, and so on.
For an order $n$ snowflake, let $A(n)$ be the number of triangles that are one layer thick, and let $B(n)$ be the number of triangles that are three layers thick. Define $G(n) = \gcd(A(n), B(n))$.
E.g. $A(3) = 30$, $B(3) = 6$, $G(3)=6$.
$A(11) = 3027630$, $B(11) = 19862070$, $G(11) = 30$.
Further, $G(500) = 186$ and $\sum_{n=3}^{500}G(n)=5124$.
Find $\displaystyle \sum_{n=3}^{10^7}G(n)$.

question:
A snowflake of order $n$ is formed by overlaying an equilateral triangle (rotated by $180$ degrees) onto each equilateral triangle of the same size in a snowflake of order $n-1$. A snowflake of order $1$ is a single equilateral triangle.
 ![image](1.png)
Some areas of the snowflake are overlaid repeatedly. In the above picture, blue represents the areas that are one layer thick, red two layers thick, yellow three layers thick, and so on.
For an order $n$ snowflake, let $A(n)$ be the number of triangles that are one layer thick, and let $B(n)$ be the number of triangles that are three layers thick. Define $G(n) = \gcd(A(n), B(n))$.
E.g. $A(3) = 30$, $B(3) = 6$, $G(3)=6$.
$A(11) = 3027630$, $B(11) = 19862070$, $G(11) = 30$.
Further, $G(500) = 186$ and $\sum_{n=3}^{500}G(n)=5124$.
Find $\displaystyle \sum_{n=3}^{10^7}G(n)$.

data_split: test

source: project euler