#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
const int N = 2e5+5, INF = 1e18, LOG = 20, MOD = 998244353;
void solve(){
int n, M;
cin >> n >> M;
vector<int> a(n+1);
for(int i = 1; i <= n; i++){
int x;
cin >> x;
a[i] = i * M - x;
}
vector<int> dp;
for(int i = 1; i <= n; i++){
if(a[i] < 0) continue;
auto it = upper_bound(dp.begin(), dp.end(), a[i]);
if(it == dp.end()){
dp.push_back(a[i]);
}
else{
*it = a[i];
}
}
cout << n - dp.size() << endl;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i++){
//cout << "Scenario #" << i << ": " << endl;
solve();
}
}
