#include "bits/stdc++.h"
using namespace std;
#define ll long long
const int MOD = 1e9+7;
const int INF = 1e9;
/**
* https://oj.uz/problem/view/LMIO19_triusis
*/
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> b;
for (int i = 1; i <= n; i++) {
if (m * i >= a[i - 1]) {
b.push_back(m * i - a[i - 1]);
}
}
vector<int> dp;
for (int i = 0; i < b.size(); i++) {
auto it = upper_bound(dp.begin(), dp.end(), b[i]);
if (it == dp.end()) {
dp.push_back(b[i]);
} else {
*it = b[i];
}
}
cout << n - dp.size() << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
// int T = 1;
// cin >> T;
// while (T--) {
solve();
// }
return 0;
}
