/*
*
* ^v^
*
*/
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <iomanip>
#include <map>
#include <numeric>
#include <functional>
#include <algorithm>
#include <set>
#include <queue>
#include <climits>
#include <cstdlib>
#include <chrono>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
// #define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define iamtefu ios_base::sync_with_stdio(false); cin.tie(0);
#define ll long long int
#define ld long double
#define fl(i,a,n) for (ll i(a); i<n; i++)
#define rfl(i,a,n) for (ll i(n-1); i>=a; i--)
#define tt int tt; cin>>tt; for(;tt--;)
template<typename F, typename S>
ostream &operator<<(ostream& os, const pair<F, S>& p){
return os << '{' << p.first << ',' << p.second << '}';
}
template<typename T>
ostream &operator<<(ostream& os, const vector<T>& v){
for (auto &x: v){
os << x << ' ';
}
os << '\n';
return os;
}
template<typename T>
ostream &operator<<(ostream& os, const set<T>& v){
for (auto &x: v){
os << x << ' ';
}
os << '\n';
return os;
}
template<typename K, typename V>
ostream &operator<<(ostream& os, const map<K, V> &mp){
os << '{';
for (auto [x, y]:mp){
os << x << ": " << y <<' ';
}
return os << "}\n";
}
ll gcd(ll a, ll b){
if (b==0){
return a;
}
return gcd(b, a%b);
}
ll pw(ll a, ll b, ll m){
ll res=1;
a%=m;
while (b){
if (b&1){
res=(res*a)%m;
}
a=(a*a)%m;
b/=2;
}
return res;
}
void scn(){
ll n, m; cin>>n>>m;
vector <ll> a(n);
fl(i,0,n){
cin>>a[i];
}
vector <ll> dp;
fl(i,0,n){
if (a[i]<=m*(i+1)){
ll jk = m*(i+1)-a[i];
ll huh = upper_bound(dp.begin(), dp.end(), jk)-dp.begin();
if (huh==dp.size()){
dp.push_back(jk);
} else {
dp[huh]=jk;
}
}
}
cout<<n-dp.size()<<'\n';
// not necessarily distinct
}
int main(){
iamtefu;
#if defined(airths)
auto t1=chrono::high_resolution_clock::now();
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
//
#endif
// tt
{
scn();
}
#if defined(airths)
auto t2=chrono::high_resolution_clock::now();
ld ti=chrono::duration_cast<chrono::nanoseconds>(t2-t1).count();
ti*=1e-6;
cerr<<"Time: "<<setprecision(12)<<ti;
cerr<<"ms\n";
#endif
return 0;
}
