#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf (int)1e15
int binsearch(int val, vector<int>& vec){
int l = 0, r = (int)vec.size()-1, mid;
while(l < r){
mid = (l + r + 1)/2;
if(vec[mid] <= val){
l = mid;
}else{
r = mid-1;
}
}
if(l != (int)vec.size() - 1 && vec[l] <= val){
l++;
}
return l;
}
void solve(){
int n, m; cin >> n >> m;
vector<int> vals;
for(int i = 0; i < n; i++){
int in;
cin >> in;
in -= (m * i);
if(in <= m){
vals.push_back(in);
}
}
if((int)vals.size() != 0LL) reverse(vals.begin(), vals.end());
vector<int> v;
//v sorted in increasing size
for(int i = 0; i < (int)vals.size(); i++){
if((int)v.size() == 0){
v.push_back(vals[i]);
continue;
}
int ind = binsearch(vals[i], v);
//strictly < in case
if(v[ind] <= vals[i]){
v.push_back(vals[i]);
}else{
v[ind] = vals[i];
}
/*cout << ind << "\n";
for(int j : v) cout << j << " ";
cout << "\n";*/
}
cout << n - (int)v.size() << "\n";
/*for(int i : v) cout << i << " ";
cout << "\n";
for(int i : vals) cout << i << " ";
cout << "\n";*/
}
signed main(){
//ios::sync_with_stdio(false), cin.tie(0);
//freopen("txt.in", "r", stdin); freopen("txt.out", "w", stdout);
//int t; cin >> t; while(t--)
solve();
}
