A virus is corrupting files on a disk. Each file is located at a distinct non-negative integer address. The virus can perform two kinds of attacks:
Direct attack: choose any file that has not yet been corrupted and corrupt it. This costs 1 unit of energy.
Shock-wave attack: choose any integer x and corrupt every file whose current address is strictly greater than x. This costs 0 energy, but after the shock-wave all remaining uncorrupted files are shifted left by k positions (their addresses are decreased by k). If any file’s address becomes ≤ 0 it is automatically corrupted for free.
You are given the initial addresses of n files and the constant k. Return the minimum energy the virus must spend to corrupt every file.
Input is two lines:
First line: two integers n and k (1 ≤ n ≤ 2·10^5, 1 ≤ k ≤ 10^9).
Second line: n distinct integers a_i (1 ≤ a_i ≤ 10^9) — the initial file addresses.
Output a single integer — the minimum energy required.