#include <iostream>
#include <vector>
#include <set>
#include <limits.h>
#include <random>
#include <array>
#include <fstream>
using namespace std;
mt19937 r, t;
struct Treap
{
int prio, dpdata, height, size, dpmin;
array<Treap*, 2> kids;
Treap(int _dpdata, int _height)
{
height = _height;
dpdata = _dpdata;
prio = r();
size = 1;
dpmin = dpdata;
kids = { NULL, NULL };
}
};
int getsize(Treap* treap)
{
return treap != NULL ? treap->size : 0;
}
int getdpmin(Treap* treap)
{
return treap != NULL ? treap->dpmin : INT_MAX;
}
void recalc(Treap* me)
{
me->dpmin = min(me->dpdata, min(getdpmin(me->kids[0]), getdpmin(me->kids[1])));
me->size = 1 + getsize(me->kids[0]) + getsize(me->kids[1]);
}
array<Treap*, 2> split(Treap* me, int x)
{
if (me == NULL) return { NULL, NULL };
if (x <= getsize(me->kids[0]))
{
array<Treap*, 2> res = split(me->kids[0], x);
me->kids[0] = res[1];
recalc(me);
return { res[0], me };
}
else
{
array<Treap*, 2>res = split(me->kids[1], x - getsize(me->kids[0]) - 1);
me->kids[1] = res[0];
recalc(me);
return { me, res[1] };
}
}
Treap* merge(Treap* left, Treap* right)
{
if (left == NULL) return right;
if (right == NULL) return left;
if (left->prio < right->prio)
{
left->kids[1] = merge(left->kids[1], right);
recalc(left);
return left;
}
else
{
right->kids[0] = merge(left, right->kids[0]);
recalc(right);
return right;
}
}
//int findidx(int x, Treap* treap, int index = -1)
//{
// if (index == -1) index = getsize(treap->kids[0]);
//
// if (treap->height == x && (treap->kids[1] == NULL || treap->kids[1]->height != x)) return index;
// if (treap->height <= x)
// {
// if (treap->kids[1] == NULL) return index;
// return findidx(x, treap->kids[1], index + getsize(treap->kids[1]->kids[0]) + 1);
// }
// else
// {
// if (treap->kids[0] == NULL) return index;
// return findidx(x, treap->kids[0], index - getsize(treap->kids[0]->kids[1]) - 1);
// }
//}
int getvalue(int idx, Treap* treap, int current = -1)
{
if (current == -1) current = getsize(treap->kids[0]);
if (idx < current) return getvalue(idx, treap->kids[0], current - getsize(treap->kids[0]->kids[1]) - 1);
if (idx > current) return getvalue(idx, treap->kids[1], current + getsize(treap->kids[1]->kids[0]) + 1);
return treap->height;
}
int bsidx(int x, Treap* treap)
{
int l = 0, r = getsize(treap), m;
while (l + 1 < r)
{
m = (l + r) / 2;
if (getvalue(m, treap) <= x) l = m;
else r = m;
}
return l;
}
int popcnt(int x)
{
int ans = 0;
while (x > 0)
{
ans += x & 1;
x >>= 1;
}
return ans;
}
int BruteForce(int n, int m, vector<int> a)
{
int i, minv = INT_MAX;
for (int mask = 0; mask < (1<<n); mask++)
{
int h = 0, pc = popcnt(mask);
if (pc >= minv) continue;
for (i = 0; i < n; i++)
{
h += m;
if (!((mask >> i) & 1))
{
if (h < a[i+1]) break;
h = a[i + 1];
}
}
if (i == n) minv = min(minv, pc);
}
return minv;
}
int main()
{
iostream::sync_with_stdio(0);
cin.tie(0);
int n, m, i;
cin >> n >> m;
vector<int> a(n+1);
for (i = 1; i <= n; i++) cin >> a[i];
a[0] = 0;
//start:
// n = 1 + r() % 10, m = r() % 10;
// a.resize(n + 1);
// for (i = 1; i <= n; i++) a[i] = r() % 10;
{
vector<Treap> storage = { Treap(n + 1, -1) }; //dp value is always offset by i
storage.reserve(n + 2);
Treap* treap = &storage[storage.size() - 1];
multiset<int> heights = { -1 };
int dis = 0, dpmin = 0, index, smaller_height;
for (i = n; i >= 0; i--)
{
set<int>::iterator it = prev(heights.upper_bound(a[i] + dis));
smaller_height = *it;
index = bsidx(smaller_height, treap);
array<Treap*, 2> parts = split(treap, index + 1);
dpmin = parts[0]->dpmin - i - 1;
storage.push_back(Treap(dpmin + i, a[i] + dis));
treap = merge(parts[0], merge(&storage[storage.size() - 1], parts[1]));
heights.insert(a[i] + dis);
dis += m;
}
cout << dpmin << '\n';
//if (BruteForce(n, m, a) == dpmin) goto start;
//else
//{
// cout << BruteForce(n, m, a) << '\n';
// cout << n << ' ' << m << '\n';
// for (i = 1; i < n + 1; i++) cout << a[i] << ' ';
//}
}
}
