У Вас есть чаша Петри с бактериями, и теперь Вы решили окунуться в этот опасный микромир. К сожалению, у Вас нет микроспопа поблизости, поэтому Вы не можете наблюдать за ними.
Вы знаете, что в чаше \(n\) бактерий и размер \(i\)-й бактерии равен \(a_i\). Также Вы знаете межгалактическую целую положительную константу \(K\).
Бактерия \(i\) может поглотить \(j\)-ю бактерию тогда и только тогда, когда \(a_i > a_j\) и \(a_i \le a_j + K\). \(j\)-я бактерия исчезает, а \(i\)-я не меняет своего размера. Бактерия может поглощать любое количество других бактерий. В каждой операции поглощения любая бактерия \(i\) может поглотить любую другую бактерию \(j\) если \(a_i > a_j\) и \(a_i \le a_j + K\). Поглощения происходят последовательно.
Например, пусть размеры бактерий \(a=[101, 53, 42, 102, 101, 55, 54]\) и \(K=1\). Одна из возможных последовательностей поглощений следующая: \([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]\). В результате \(3\) бактерии останутся в чаше Петри.
Так как у Вас нет микроскопа, Вы можете только гадать, какое минимальное возможное количество бактерий может остаться в Вашей чашке Петри, когда Вы наконец найдете себе какой-нибудь микроскоп.
Примечание
Первый пример описан в условии задачи.
Во втором примере одно из оптимальных решений следующее: \([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]\).
В третьем примере никакая бактерия не может поглотить никакую другую.