#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e9 + 5;
int solve() {
int n, m;
cin >> n >> m;
vector<int> v;
for (int i = 0; i < n; i++) {
int a; cin >> a;
if (a <= m * (i + 1)) v.push_back(m * (i + 1) - a);
}
vector<int> dp(v.size() + 1, INF);
dp[0] = 0;
for (int i = 0; i < v.size(); i++) {
int idx = upper_bound(dp.begin(), dp.end(), v[i]) - dp.begin();
if (v[i] < dp[idx]) dp[idx] = v[i];
}
int ans = 0;
for (int i = 1; i <= v.size(); i++) {
if (dp[i] < INF) ans = i;
}
return n - ans;
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << solve();
return 0;
}
