//Rabbit Carrot
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <utility>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <climits>
#pragma GCC optimize("-Ofast")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#define ll long long
#define ull unsigned long long
#define Youssef_Bahy ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define Num_of_Digits(n) ((int)log10(n) + 1)
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define read(type) readInt<type>()
#define popcount(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
#define popcountll(x) __builtin_popcountll(x)
#define clzll(x) __builtin_clzll(x)
#define ctzll(x) __builtin_ctzll(x)
#define lg(x) 31-clz(x)
#define lgll(x) 63-clzll(x)
#define all(v) v.begin(),v.end()
using namespace std;
const int N=5000+5,INF=1e9;
const ll OO=1e118;
ll t=1;
int dr[]={1, 0, -1, 0};
int dc[]={0, 1, 0, -1};
void solve()
{
ll n, m;
cin>>n>>m;
vector<ll>a(n);
for(auto&x: a) cin>>x;
vector<ll>dp;
vector<ll>b;
for(ll i=0;i<n;i++) {
if(m*(i+1)-a[i]>=0) b.push_back(m*(i+1)-a[i]);
}
for(ll i=0;i<b.size();i++) {
ll j=(int)(upper_bound(dp.begin(), dp.end(), b[i])-dp.begin());
if(j==dp.size()) dp.push_back(b[i]);
else dp[j]=b[i];
}
cout<<n-dp.size()<<'\n';
}
int main()
{
Youssef_Bahy
// cin>>t;
while(t--)
solve();
}
