///TRAN THAI BAO :3
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
#define maxN 1000007
//a[j] - a[i] <= (j-i)*m
///a[j] - j*m <= a[i] - i*m
int n, m;
long long a[maxN] = {0};
long long u[maxN] = {0};
vector<int>dp;
void solve()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
u[i] = (long long)i*m - a[i];
if(a[i] > i*m)
continue;
vector<int>::iterator it = upper_bound(dp.begin(), dp.end(), u[i]);
if(it == dp.end())
dp.push_back(u[i]);
else dp[distance(dp.begin(), it)] = u[i];
}
cout << n-dp.size();
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
