#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll _Gcd(int a, int b) { return b == 0 ? a : _Gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a * b) / _Gcd(a, b); }
bool prime(int n)
{
if (n < 2)
return false;
for (int x = 2; x * x <= n; x++)
if (n % x == 0)
return false;
return true;
}
ll mod = 998244353;
ll power(ll a, ll b, ll mod = 1e9 + 7)
{
ll result = 1;
while (b > 0)
{
if (b & 1)
{
result = (result * a) % mod;
}
a = (a * a) % mod;
b >>= 1;
}
return result;
}
int lowbit(int x)
{
return x & (-x);
}
int xorFrom1To(int n)
{
if (n % 4 == 0)
return n;
else if (n % 4 == 1)
return 1;
else if (n % 4 == 2)
return n + 1;
else
return 0;
}
int factorial(int n)
{
if (n <= 1)
return 1;
return n * factorial(n - 1);
}
/*const int MAX_N = 1e6;
// max_div[i] contains the largest prime that goes into i
int max_div[MAX_N + 1];
void seive() {
for (int i = 2; i <= MAX_N; i++) {
if (max_div[i] == 0) {
for (int j = i; j <= MAX_N; j += i) { max_div[j] = i; }
}
}
}*/
vector<int> factor(int n)
{ // O (racine de n)
vector<int> ret;
for (int i = 2; i * i <= n; i++)
{
while (n % i == 0)
{
ret.push_back(i);
n /= i;
}
}
if (n > 1)
{
ret.push_back(n);
}
return ret;
}
int phi(int n)
{ // counts the number of positive integers in the interval [1,n] which are coprime to n
int ans = n;
for (int p = 2; p * p <= n; p++)
{
if (n % p == 0)
{
while (n % p == 0)
{
n /= p;
}
ans -= ans / p;
}
}
if (n > 1)
{
ans -= ans / n;
}
return ans;
}
void solve()
{
ll n, t, s, m,d, q;
cin >> n >> m;
vector<ll> v(n),u, dp;
for (int i = 0; i <n; i++){
cin>>v[i];
}
for (int i = 1; i <=n; i++)
{
if(m*i>=v[i-1]) u.push_back(m*i-v[i-1]);
}
for (int i : u)
{
int pos = upper_bound(dp.begin(), dp.end(), i) - dp.begin();//upper instead of lower bc not strictly increesing
if (pos == dp.size())
{
dp.push_back(i);
}
else
{
dp[pos] = i;
}
}
cout << n-dp.size() << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q = 1;
// cin >> q;
while (q--)
{
solve();
}
}
