#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)
//another number for hashing:b(137) only
// freopen("deleg.in", "r", stdin);
// freopen("deleg.out", "w", stdout);
class BinaryIndexedTree{
private:
vector<ll>bits;
public:
BinaryIndexedTree(ll n){
bits.resize(n);
}
void update(ll index, ll delta){
while(index<bits.size()){
bits[index]=max(bits[index],delta);
index+=index&-index;
}
}
ll query(ll index){
ll ans=0;
while(index>0){
ans=max(ans,bits[index]);
index-=index&-index;
}
return ans;
}
};
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>v2;
for(ll i=0; i<n; i++){
if((i+1)*m-a[i]>=0){
v.push_back((i+1)*m-a[i]);
v2.push_back(v.back());
}
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
unordered_map<ll,ll>mp;
for(ll i=0; i<v.size(); i++){
mp[v[i]]=i+1;
}
vector<ll>cur(v2.size(),0); BinaryIndexedTree BIT(v2.size()+10);
for(ll i=0; i<v2.size(); i++){
cur[i]=mp[v2[i]];
}
vector<ll>dp(v2.size()+10,0);
for(ll i=0; i<v2.size(); i++){
dp[i]=BIT.query(cur[i])+1;
BIT.update(cur[i],dp[i]);
}
cout<<n-*max_element(dp.begin(),dp.end())<<endl;
}
