#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n + 1), b, min_lis;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 1; i <= n; ++i) {
if (m * i >= a[i]) b.push_back(m * i - a[i]);
}
if (b.empty()) {
cout << n << '\n';
return;
}
int sz = b.size();
for (int i = 0; i < sz; ++i) {
auto upp = upper_bound(min_lis.begin(), min_lis.end(), b[i]);
if (upp == min_lis.end())
min_lis.push_back(b[i]);
else
*upp = b[i];
}
cout << n - min_lis.size() << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
