#include <bits/stdc++.h>
using namespace std;
#define ar array
#define ll long long
const int inf = 2e9;
#define int long long
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n + 1, 0);
for (int i = 1; i <= n;i++)
cin >> a[i];
vector<int> dp = {0};
for (int i = 1; i <= n; i++) {
if (a[i] > m * i)
continue;
int x = m * i - a[i];
int j = lower_bound(dp.begin(), dp.end(), x + 1) - dp.begin();
if (j == dp.size())
dp.push_back(x);
else
dp[j] = x;
}
cout << n - dp.size() + 1;
}
int32_t main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
return 0;
}
