#include <bits/stdc++.h> #define int long long using namespace std; class SegTree { private: int sz; vector<int> tree; public: SegTree(int len): sz(len),tree(4*len,0){} void update(int ind,int val) { ind+=sz; tree[ind] = max(tree[ind],val); while (ind>1) { ind>>=1; tree[ind] = max(tree[ind*2],tree[ind*2+1]); } } int query(int l,int r) { int res=0; l+=sz; r+=sz; while (l<=r) { if (l&1) res = max(res,tree[l++]); if (!(r&1)) res = max(res,tree[r--]); l>>=1; r>>=1; } return res; } } ; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); //freopen("rabbit.in","r",stdin); int n,m; cin>>n>>m; vector<int> a(n+1,0); vector<int> all(n+1,0); for (int i=1;i<=n;i++) { int x; cin>>x; a[i] = x-i*m; all[i] = a[i]; } sort(begin(all),end(all)); reverse(begin(a),end(a)); for (auto &i:a) i = lower_bound(begin(all),end(all),i)-begin(all)+1; int mx=1; for (auto i:a) mx = max(mx,i+1); SegTree segtree(mx); for (auto i:a) { int ml=segtree.query(0,i)+1; segtree.update(i,ml); } cout<<n+1-segtree.query(a[n],a[n]); return 0; }