#include<bits/stdc++.h> using namespace std; #define ll long long signed main() { ll n,m; cin>>n>>m; vector<ll> a(n); for(int i=0;i<n;i++) { cin>>a[i]; a[i]-=i*m; a[i]=-a[i]; } vector<ll> lis(1,-m); for(auto&x:a) { if(lis.size()==0 || lis.back()<=x) lis.emplace_back(x); else { auto it = upper_bound(lis.begin(),lis.end(),x); if(*it==-m) continue; *it = x; } } cout<<n+1-lis.size(); return 0; }