#include<bits/stdc++.h>
#include<random>
using namespace std;
using db=double;
using ll=long long;
using sll=__int128;//super long long
using lb=long double;//lb is slow
//numbers for hashing: b(19260817),mod(998244353)
// freopen("lasers.in", "r", stdin);
// freopen("lasers.out", "w", stdout);
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n,m; cin>>n>>m; vector<ll>a(n);
for(ll i=0; i<n; i++){
cin>>a[i];
}
vector<ll>v; vector<ll>dp;
for(ll i=0; i<n; i++){
if((i+1)*m-a[i]>=0){
v.push_back((i+1)*m-a[i]);
}
}
for(auto x:v){
ll pos=upper_bound(dp.begin(),dp.end(),x)-dp.begin();
if(pos==dp.size())dp.push_back(x);
else dp[pos]=x;
}
ll ans=n-dp.size(); cout<<ans<<'\n';
}
