{"raw_statement":[{"iden":"statement","content":"You have a Petri dish with bacteria and you are preparing to dive into the harsh micro-world. But, unfortunately, you don't have any microscope nearby, so you can't watch them.\n\nYou know that you have $n$ bacteria in the Petri dish and size of the $i$\\-th bacteria is $a_i$. Also you know intergalactic positive integer constant $K$.\n\nThe $i$\\-th bacteria can swallow the $j$\\-th bacteria if and only if $a_i &gt; a_j$ and $a_i \\le a_j + K$. The $j$\\-th bacteria disappear, but the $i$\\-th bacteria doesn't change its size. The bacteria can perform multiple swallows. On each swallow operation any bacteria $i$ can swallow any bacteria $j$ if $a_i &gt; a_j$ and $a_i \\le a_j + K$. The swallow operations go one after another.\n\nFor example, the sequence of bacteria sizes $a=[101, 53, 42, 102, 101, 55, 54]$ and $K=1$. The one of possible sequences of swallows is: $[101, 53, 42, 102, \\underline{101}, 55, 54]$ $\\to$ $[101, \\underline{53}, 42, 102, 55, 54]$ $\\to$ $[\\underline{101}, 42, 102, 55, 54]$ $\\to$ $[42, 102, 55, \\underline{54}]$ $\\to$ $[42, 102, 55]$. In total there are $3$ bacteria remained in the Petri dish.\n\nSince you don't have a microscope, you can only guess, what the minimal possible number of bacteria can remain in your Petri dish when you finally will find any microscope."},{"iden":"input","content":"The first line contains two space separated positive integers $n$ and $K$ ($1 \\le n \\le 2 \\cdot 10^5$, $1 \\le K \\le 10^6$) — number of bacteria and intergalactic constant $K$.\n\nThe second line contains $n$ space separated integers $a_1, a_2, \\dots, a_n$ ($1 \\le a_i \\le 10^6$) — sizes of bacteria you have."},{"iden":"output","content":"Print the only integer — minimal possible number of bacteria can remain."},{"iden":"examples","content":"Input\n\n7 1\n101 53 42 102 101 55 54\n\nOutput\n\n3\n\nInput\n\n6 5\n20 15 10 15 20 25\n\nOutput\n\n1\n\nInput\n\n7 1000000\n1 1 1 1 1 1 1\n\nOutput\n\n7"},{"iden":"note","content":"The first example is clarified in the problem statement.\n\nIn the second example an optimal possible sequence of swallows is: $[20, 15, 10, 15, \\underline{20}, 25]$ $\\to$ $[20, 15, 10, \\underline{15}, 25]$ $\\to$ $[20, 15, \\underline{10}, 25]$ $\\to$ $[20, \\underline{15}, 25]$ $\\to$ $[\\underline{20}, 25]$ $\\to$ $[25]$.\n\nIn the third example no bacteria can swallow any other bacteria."}],"translated_statement":[{"iden":"statement","content":"你有一个含有细菌的培养皿，正准备深入这个严酷的微观世界。但不幸的是，你附近没有显微镜，因此无法观察它们。\n\n你知道培养皿中有 $n$ 个细菌，第 $i$ 个细菌的大小为 $a_i$。你还知道一个星际正整数常数 $K$。\n\n第 $i$ 个细菌可以吞掉第 $j$ 个细菌，当且仅当 $a_i > a_j$ 且 $a_i lt.eq a_j + K$。被吞掉的 $j$-th 细菌会消失，但吞食的 $i$-th 细菌大小不变。细菌可以执行多次吞食操作。每次吞食操作中，任何细菌 $i$ 都可以吞食任何满足 $a_i > a_j$ 且 $a_i lt.eq a_j + K$ 的细菌 $j$。吞食操作依次进行。\n\n例如，细菌大小序列为 $a = [ 101, 53, 42, 102, 101, 55, 54 ]$ 且 $K = 1$。一种可能的吞食序列是：$[ 101, 53, 42, 102, underline(101), 55, 54 ]$ $arrow.r$ $[ 101, underline(53), 42, 102, 55, 54 ]$ $arrow.r$ $[ underline(101), 42, 102, 55, 54 ]$ $arrow.r$ $[ 42, 102, 55, underline(54) ]$ $arrow.r$ $[ 42, 102, 55 ]$。最终培养皿中剩余 $3$ 个细菌。\n\n由于你没有显微镜，只能猜测：当你最终找到显微镜时，培养皿中可能剩余的最少细菌数量是多少？\n\n第一行包含两个用空格分隔的正整数 $n$ 和 $K$（$1 lt.eq n lt.eq 2 dot.op 10^5$，$1 lt.eq K lt.eq 10^6$）——细菌数量和星际常数 $K$。\n\n第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq 10^6$）——你拥有的细菌大小。\n\n请输出一个整数——可能剩余的最少细菌数量。\n\n第一个例子已在题面中说明。\n\n在第二个例子中，最优的吞食序列是：$[ 20, 15, 10, 15, underline(20), 25 ]$ $arrow.r$ $[ 20, 15, 10, underline(15), 25 ]$ $arrow.r$ $[ 20, 15, underline(10), 25 ]$ $arrow.r$ $[ 20, underline(15), 25 ]$ $arrow.r$ $[ underline(20), 25 ]$ $arrow.r$ $[ 25 ]$。\n\n在第三个例子中，没有任何细菌能吞食其他细菌。"},{"iden":"input","content":"第一行包含两个用空格分隔的正整数 $n$ 和 $K$（$1 lt.eq n lt.eq 2 dot.op 10^5$，$1 lt.eq K lt.eq 10^6$）——细菌数量和星际常数 $K$。第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq 10^6$）——你拥有的细菌大小。"},{"iden":"output","content":"请输出一个整数——可能剩余的最少细菌数量。"},{"iden":"examples","content":"输入\n7 1\n101 53 42 102 101 55 54\n输出\n3\n\n输入\n6 5\n20 15 10 15 20 25\n输出\n1\n\n输入\n7 1000000\n1 1 1 1 1 1 1\n输出\n7"},{"iden":"note","content":"第一个例子已在题面中说明。\n在第二个例子中，最优的吞食序列是：$[ 20, 15, 10, 15, underline(20), 25 ]$ $arrow.r$ $[ 20, 15, 10, underline(15), 25 ]$ $arrow.r$ $[ 20, 15, underline(10), 25 ]$ $arrow.r$ $[ 20, underline(15), 25 ]$ $arrow.r$ $[ underline(20), 25 ]$ $arrow.r$ $[ 25 ]$。\n在第三个例子中，没有任何细菌能吞食其他细菌。"}],"sample_group":[],"show_order":[],"formal_statement":"Given:\n- A multiset $ A = \\{a_1, a_2, \\dots, a_n\\} $ of positive integers representing bacterial sizes.\n- A positive integer constant $ K $.\n\nDefinition:  \nBacteria $ i $ can swallow bacteria $ j $ if and only if:  \n$$\na_i > a_j \\quad \\text{and} \\quad a_i \\leq a_j + K\n$$\n\nGoal:  \nFind the **minimum possible number of bacteria remaining** after any sequence of valid swallows (each swallow removes one bacterium; swallows can be performed in any order, and a bacterium may swallow multiple others sequentially).\n\n---\n\n**Formal Problem Statement:**\n\nLet $ A $ be a multiset of $ n $ positive integers, and $ K \\in \\mathbb{Z}^+ $.  \nDefine a directed relation $ \\rightarrow $ on $ A $:  \n$$\na_i \\rightarrow a_j \\iff a_i > a_j \\text{ and } a_i \\leq a_j + K\n$$\n\nA swallow sequence is a sequence of removals where each removed element $ a_j $ is swallowed by some remaining element $ a_i $ satisfying the above condition.\n\nWe wish to find the **minimum number of elements** that can remain after any sequence of such swallows.\n\n---\n\n**Key Insight:**  \nThis is equivalent to covering the multiset $ A $ with the **fewest possible \"survivor\" bacteria**, such that every non-survivor bacterium $ a_j $ is swallowed by some survivor $ a_i $, i.e., $ a_i \\in (a_j, a_j + K] $.\n\nEquivalently:  \nWe want to partition $ A $ into as few subsets as possible, where in each subset, there is **one survivor** and all other elements can be \"covered\" by it — meaning each element $ x $ in the subset satisfies $ x \\leq \\text{survivor} \\leq x + K $.\n\nTo minimize the number of survivors, we can use a **greedy algorithm** on sorted data:\n\n1. Sort the multiset $ A $ in non-decreasing order.\n2. Traverse the sorted list and greedily assign each bacterium to the earliest possible survivor that can swallow it.\n\nBut note: a survivor can swallow **multiple** bacteria, as long as each is in $ (x, x+K] $.\n\nActually, the optimal strategy is:\n\n- Sort $ A $: $ b_1 \\leq b_2 \\leq \\dots \\leq b_n $\n- Use a greedy grouping: Start with the smallest unassigned bacterium as a survivor. Then, all bacteria that are $ \\leq \\text{survivor} + K $ can be swallowed by it.\n- So, the survivor can \"cover\" a contiguous segment of bacteria from its own value up to its value + K.\n- Then move to the first bacterium not covered and make it the next survivor.\n\nThis is equivalent to the **minimum number of intervals** of length $ K $ needed to cover all points, where each interval is $ [s, s+K] $ and must contain the point $ s $ (since the survivor must be present and swallow others).\n\nActually, more precisely:  \nEach survivor at value $ s $ can swallow any bacterium $ x $ such that $ s - K \\leq x < s $.  \nBut since $ s $ must be in the set, and we are covering all elements, we can reframe:\n\nWe want to cover all elements with the **minimum number of points** $ s_i $, such that for every element $ x $, there exists some $ s_i $ with:  \n$$\nx \\in (s_i - K, s_i]\n$$\n\nThis is equivalent to:  \nCover the multiset $ A $ with intervals of the form $ (s - K, s] $, where $ s \\in A $, and minimize the number of such intervals.\n\nThis is a classic **interval covering problem** on the line.\n\n**Optimal greedy algorithm:**\n\n1. Sort the array: $ b_1 \\leq b_2 \\leq \\dots \\leq b_n $\n2. Initialize:\n   - survivors = 0\n   - last_survivor = -∞\n3. For each $ b_i $ in sorted order:\n   - If $ b_i > \\text{last\\_survivor} + K $, then we need a new survivor at $ b_i $, because no previous survivor can swallow $ b_i $.\n   - Otherwise, $ b_i $ can be swallowed by the last survivor.\n\nWhy?  \nBecause if the last survivor was placed at $ s $, then it can swallow any $ x \\in (s - K, s] $.  \nBut since we process in increasing order, and we place a survivor at $ b_i $ only when $ b_i > \\text{last\\_survivor} + K $, then:\n\n- The previous survivor $ s $ can swallow all $ x \\leq s + K $.\n- So if $ b_i \\leq s + K $, it can be swallowed.\n- If $ b_i > s + K $, then even the largest value $ s + K $ is less than $ b_i $, so $ s $ cannot swallow $ b_i $, and we need a new survivor.\n\nThus, the algorithm:\n\n```plaintext\nSort A\nsurvivors = 0\nlast_s = -inf\n\nfor each a in sorted(A):\n    if a > last_s + K:\n        survivors += 1\n        last_s = a\n```\n\nThen output `survivors`.\n\n---\n\n**Final Formal Output:**\n\nLet $ A = \\{a_1, a_2, \\dots, a_n\\} $ be a multiset of positive integers, and $ K \\in \\mathbb{Z}^+ $.  \nSort $ A $ in non-decreasing order: $ b_1 \\leq b_2 \\leq \\dots \\leq b_n $.  \nDefine:\n\n$$\n\\text{min\\_survivors} = \\min \\left\\{ m \\in \\mathbb{N} \\,\\middle|\\, \\exists \\, s_1 \\leq s_2 \\leq \\dots \\leq s_m \\in A \\text{ s.t. } \\forall i \\in [n], \\exists j \\in [m] \\text{ with } b_i \\in (s_j - K, s_j] \\right\\}\n$$\n\nThis minimum is computed by the greedy algorithm:\n\n$$\n\\boxed{\n\\begin{aligned}\n&\\text{Sort } b_1 \\leq b_2 \\leq \\dots \\leq b_n \\\\\n&\\text{Set } \\text{count} = 0, \\text{ last} = -\\infty \\\\\n&\\text{For } i = 1 \\text{ to } n: \\\\\n&\\quad \\text{If } b_i > \\text{last} + K: \\\\\n&\\quad\\quad \\text{count} \\gets \\text{count} + 1 \\\\\n&\\quad\\quad \\text{last} \\gets b_i \\\\\n&\\text{Return } \\text{count}\n\\end{aligned}\n}\n$$","simple_statement":null,"has_page_source":false}