#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<set>
#include<algorithm>
#define ll long long 
#define ddq set<poi>::iterator
using namespace std;
const int maxn=500010;
const ll inf=1e18+233;
struct sgt{int pos[2]; ll mn[2], delta[2];}tr[maxn<<2];
struct poi{int pos; ll w;};
bool operator < (poi a, poi b) {return a.pos<b.pos;}
int n, D;
int a[maxn];
set<poi>s1, s2;

template<typename T>
inline void read(T &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;
}

inline void up(int x)
{
    for(int i=0;i<2;i++)
    if(tr[x<<1].mn[i]<tr[x<<1|1].mn[i])
    {
        tr[x].mn[i]=tr[x<<1].mn[i];
        tr[x].pos[i]=tr[x<<1].pos[i];
    }
    else
    {
        tr[x].mn[i]=tr[x<<1|1].mn[i];
        tr[x].pos[i]=tr[x<<1|1].pos[i];   
    }
}

void build(int x, int l, int r)
{
    if(l==r)
    {
        if(l==1) tr[x].mn[0]=tr[x].mn[1]=inf;
        else tr[x].mn[0]=a[l]+a[1]+1ll*(l-1)*D, tr[x].mn[1]=a[l]-1ll*l*D+inf;
        tr[x].pos[0]=tr[x].pos[1]=l;
        return;
    }

    int mid=(l+r)>>1;
    build(x<<1, l, mid); build(x<<1|1, mid+1, r);

    up(x);
    // printf("x:%d l:%d r:%d mn0:%lld pos0:%d mn1:%lld pos1:%d\n", x, l, r, tr[x].mn[0], tr[x].pos[0], tr[x].mn[1], tr[x].pos[1]);
}

inline void addone(int x, ll delta, int ty)
{
    tr[x].mn[ty]+=delta;
    tr[x].delta[ty]+=delta;
}

inline void down(int x)
{
    for(int i=0;i<2;i++)
        if(tr[x].delta[i])
            addone(x<<1, tr[x].delta[i], i), addone(x<<1|1, tr[x].delta[i], i);

    tr[x].delta[0]=tr[x].delta[1]=0;
}

void updateset(int x, int l, int r, int cx)
{
    if(l==r) return (void)(tr[x].mn[0]=tr[x].mn[1]=inf);

    down(x);

    int mid=(l+r)>>1;
    if(cx<=mid) updateset(x<<1, l, mid, cx);
    else updateset(x<<1|1, mid+1, r, cx);

    up(x);

    // printf("x:%d l:%d r:%d tr[x].mn[0]:%lld tr[x].pos[0]:%d\n", x, l, r, tr[x].mn[0], tr[x].pos[0]);
    // printf("x:%d l:%d r:%d tr[x].mn[1]:%lld tr[x].pos[1]:%d\n", x, l, r, tr[x].mn[1], tr[x].pos[1]);
}

void update(int x, int l, int r, int cl, int cr, ll delta, int ty)
{
    if(cl<=l && r<=cr) return addone(x, delta, ty);

    down(x);

    int mid=(l+r)>>1;
    if(cl<=mid) update(x<<1, l, mid, cl, cr, delta, ty);
    if(cr>mid) update(x<<1|1, mid+1, r, cl, cr, delta, ty);

    up(x);
}

inline void insert(int x)
{
    // printf("x:%d\n", x);
    ll delta=a[x]-1ll*x*D;
    ddq pos=s1.lower_bound((poi){x, delta}); 
    ddq pre=pos; pre--;
    if(pre->w>delta)
    {
        ddq it=pos; //printf("it->w:%lld\n", it->w);
        for(;it!=s1.end() && it->w>=delta;it++)
        {
            ddq nxt=it; it++;
            update(1, 1, n, it->pos, nxt->pos-1, -it->w+delta, 0);
            // printf("iterator->w:%lld\n", it->w);
        }
        update(1, 1, n, x, pos->pos-1, delta-pre->w, 0);
        s1.erase(pos, it); 
        s1.insert((poi){x, delta}); 
    }

    delta=a[x]+1ll*x*D;
    pos=s2.lower_bound((poi){x, delta});
    // if(x==4) printf("x:%d delta:%lld pos->w:%lld\n", x, delta, pos->w);
    if(pos->w>delta)
    {
        ddq it=pos;
        while(it!=s2.begin())
        {
            it--;
            if(it->w<delta)
            {
                it++; break;
            }
            else 
            {
                ddq pre=it; pre--;
                // printf("change:: L:%d R:%d it->w:%lld delta:%lld\n", pre->pos+1, it->pos, it->w, delta);
                update(1, 1, n, pre->pos+1, it->pos, -it->w+delta, 1);
            }   
        }
        pre=pos; pre--;
        // printf("pre->pos+1:%d x:%d delta:%lld pos->w:%lld\n", pre->pos+1, x, delta, pos->w);
        update(1, 1, n, pre->pos+1, x, delta-pos->w, 1);
        s2.erase(it, pos);
        s2.insert((poi){x, delta});
    }

    updateset(1, 1, n, x);
}

int main()
{
    read(n); read(D);
    for(int i=1;i<=n;i++) read(a[i]);

    build(1, 1, n);

    s1.insert((poi){1, a[1]-D}); s1.insert((poi){n+1, -inf});
    s2.insert((poi){1, -inf}); s2.insert((poi){n+1, inf});
    ll ans=0;
    for(int i=1;i<n;i++)
    {
        ll mn0=tr[1].mn[0]; int pos0=tr[1].pos[0];
        ll mn1=tr[1].mn[1]; int pos1=tr[1].pos[1];
        // printf("i:%d mn0:%lld pos0:%d mn1:%lld pos1:%d\n", i, mn0, pos0, mn1, pos1);

        if(mn0<mn1) ans+=mn0, insert(pos0);
        else ans+=mn1, insert(pos1);
    }

    printf("%lld\n", ans);
}


Measured memory_bytes: 46464