#include <bits/stdc++.h> using namespace std; #define forn(i, n) for(ll i = 0; i < (n); ++i) #define for1(i, n) for(ll i = 1; i <= (n); ++i) #define chmin(a, b) ((a) = min(a, b)) #define all(x) (x).begin(), (x).end() #define dbg(x) cout << #x << " = " << (x) << endl; using ll = long long; using vi = vector<int>; const int oo = 1e7; void compress(vi& v) { sort(all(v)); v.erase(unique(all(v)), v.end()); } const int MAXN = 2e5 + 2; ll n, m; int a[MAXN]; vi v; int rnk(int x) { return lower_bound(all(v), x) - v.begin(); } int N; class SegmentTree { vi info; #define set_m int m = l + (r - l) / 2; #define left l, m, 2*p #define right m+1, r, 2*p+1 #define in_range (i <= l and r <= j) void up(int p) { info[p] = min(info[2*p], info[2*p+1]); } public: SegmentTree() = default; SegmentTree(int n) { N = n + 3; info = vi(4*N, oo); } void set(int k, int x, int l=0, int r=N, int p=1) { if (l == r) { info[p] = x; return; } set_m; if (k <= m) set(k, x, left); if (k > m) set(k, x, right); up(p); } int query(int i, int j, int l=0, int r=N, int p=1) { if in_range return info[p]; set_m; int ans = oo; if (i <= m) chmin(ans, query(i, j, left)); if (j > m) chmin(ans, query(i, j, right)); return ans; } void update(int k, int x) { int prv = query(k, k); if (x < prv) set(k, x); } void print() { cout << "[ "; for (int i = 0; i <= N; ++i) cout << query(i, i) << ' '; cout << "]\n"; } }; SegmentTree st; #define mret return mem[i] = int mem[MAXN]; int f(int i) { if (i == -1) return 0; if (mem[i] != -1) return mem[i]; // int ans = oo; // for (int j = i; j >= 0; --j) // if (a[j] - j * m >= a[i + 1] - (i + 1) * m) // chmin(ans, f(j - 1) - j); // mret i + ans; int r = rnk(a[i + 1] - (i + 1) * m); int res = st.query(r, N); res = i + res; st.update(r, res - (i + 1)); // dbg(i + 1) dbg(a[i + 1] - (i + 1) * m) dbg(r) // st.print(); mret res; } int main() { cin >> n >> m; for1(i, n) cin >> a[i]; forn(j, n+3) v.push_back(a[j] - j * m); compress(v); st = SegmentTree(n); st.set(rnk(0), 0); // st.print(); forn(i, n+2) mem[i] = -1; forn(i, n+1) f(i); cout << f(n); }