#include <iostream>
#include <vector>
#include <set>
#include <limits.h>
#include <random>
#include <array>
using namespace std;
mt19937 r;
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 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;
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 = findidx(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;
}
