#include <bits/stdc++.h>
#define C make_pair
#define ll long long
#define all(a) a.begin(),a.end()
#define name "task"
#define ln "\n"
using namespace std;
ll n,M;
const int maxn=2*1e5;
ll a[maxn+9];
void solve(){
	cin>>n>>M;
	for(int i=1;i<=n;++i)
		cin>>a[i];
	vector<ll> dp;
	//memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;++i){
		if(a[i]<=i*M){
			auto it=upper_bound(all(dp),i*M-a[i]);
			if(it==dp.end())
				dp.push_back(i*M-a[i]);
			else
				*it=i*M-a[i];
		}
	}
	cout<<n-dp.size();
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if(fopen(name".inp","r")){
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    solve();
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgQyBtYWtlX3BhaXIKI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSBhbGwoYSkgYS5iZWdpbigpLGEuZW5kKCkKI2RlZmluZSBuYW1lICJ0YXNrIgojZGVmaW5lIGxuICJcbiIKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKbGwgbixNOwpjb25zdCBpbnQgbWF4bj0yKjFlNTsKbGwgYVttYXhuKzldOwp2b2lkIHNvbHZlKCl7CgljaW4+Pm4+Pk07Cglmb3IoaW50IGk9MTtpPD1uOysraSkKCQljaW4+PmFbaV07Cgl2ZWN0b3I8bGw+IGRwOwoJLy9tZW1zZXQoZHAsMCxzaXplb2YoZHApKTsKCWZvcihpbnQgaT0xO2k8PW47KytpKXsKCQlpZihhW2ldPD1pKk0pewoJCQlhdXRvIGl0PXVwcGVyX2JvdW5kKGFsbChkcCksaSpNLWFbaV0pOwoJCQlpZihpdD09ZHAuZW5kKCkpCgkJCQlkcC5wdXNoX2JhY2soaSpNLWFbaV0pOwoJCQllbHNlCgkJCQkqaXQ9aSpNLWFbaV07CgkJfQoJfQoJY291dDw8bi1kcC5zaXplKCk7Cn0KaW50IG1haW4oKXsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7IGNpbi50aWUoMCk7IGNvdXQudGllKDApOwogICAgaWYoZm9wZW4obmFtZSIuaW5wIiwiciIpKXsKICAgICAgICBmcmVvcGVuKG5hbWUiLmlucCIsInIiLHN0ZGluKTsKICAgICAgICBmcmVvcGVuKG5hbWUiLm91dCIsInciLHN0ZG91dCk7CiAgICB9CiAgICBzb2x2ZSgpOwp9Cg==

NSA0MDAKMzAwCjcwMAoyMDAKMTAwMAo1MDA=

5 400
300
700
200
1000
500