#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define UNSYNC ios::sync_with_stdio(false); cin.tie(nullptr);
#define all(x) x.begin(), x.end()
#define rep(i, ini, x) for (int i = ini; i < x; ++i)
#define per(i, fin, x) for (int i = fin; i >= x; --i)
const int MOD = 1e9 + 7;
int main()
{
UNSYNC
int N, M; cin >> N >> M;
vector<int> A (N); rep(i, 0, N) cin >> A[i];
vector<int> F;
rep(i, 0, N){
if (M * (i + 1) >= A[i]){
F.push_back(M * (i + 1) - A[i]);
}
}
int S = F.size();
vector<i64> dp (S + 1, MOD); dp[0] = -MOD;
rep(i, 0, S){
i64 l = upper_bound(all(dp), F[i]) - dp.begin();
dp[l] = F[i];
}
i64 ans = 0;
rep(i, 0, S + 1){
if (dp[i] < MOD) ans = i;
}
cout << N - ans << '\n';
return 0;
}
