#include <bits/stdc++.h>
using namespace std;
#define int long long
using ld = long double;
using pr = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
using vv = vector<vector<int>>;
const int INF = 1e18+1, MOD = 1e9+7, MAXN = 4e5+5, MAXA = 41;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n+2, 0);
for (int i = 1; i <= n; i++) cin >> a[i];
vector<int> dp;
for (int i = 1; i <= n; i++) {
if (i * m < a[i]) continue;
int val = i * m - a[i];
auto it = upper_bound(dp.begin(), dp.end(), val) - dp.begin();
if (it == dp.size()) dp.pb(val);
else dp[it] = val;
}
cout << n - dp.size();
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// int T;
// cin >> T;
// while (T--)
solve();
}
