stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

using namespace std;



using ll = long long;

const ll INF = 1LL << 50;





 int main(void) {

 int N, M;

 cin >> N >> M;



 const int NMAX = 1000;

 const int MMAX = 2000;

 int a[MMAX], b[MMAX];

 ll c[MMAX];



 for (int i = 0; i < M; ++i) {

 cin >> a[i] >> b[i] >> c[i];

 c[i] = -c[i];

 }



 ll dist[NMAX];



 for (int i = 0; i < N; ++i) {

 dist[i] = INF;

 }



 dist[0] = 0;





for (int loop = 0; loop < N - 1; ++ loop) {

for (int i = 0; i < M; ++i) {



 if (dist[a[i] - 1] == INF) continue;



 if (dist[b[i] - 1] > dist[a[i] - 1] + c[i]) {

 dist[b[i] - 1] = dist[a[i] - 1] + c[i];

 }

 }

 }



 ll ans = dist[N - 1];





 bool negative[NMAX];



 for (int i = 0; i < N; ++i) {

 negative[i] = false;

 }



 for (int loop = 0; loop < N ; ++ loop) {

 for (int i = 0; i < M; ++i) {

 if (dist[a[i] - 1] == INF) continue;



 if (dist[b[i] - 1] > dist[a[i] - 1] + c[i]) {

 dist[b[i] - 1] = dist[a[i] - 1] + c[i];

 negative[b[i] - 1] = true;

 }



 if (negative[a[i] - 1] == true) {

 negative[b[i] - 1] = true;

 }

 }

 }





 if (negative[N - 1])

 cout << "inf" << endl;

 else

 cout << -ans << endl;



 return 0;

 }


// Faster C++ solution for the same problem (measured speedup: 5.207319007186186x):
#include <cstdio>

#include <cstdlib>

#include <vector>



using namespace std;



struct edge {

	int from;

	int to;

	long long cost;

};

edge es[2000];

long long d[1000];

int num[1000];

int N,M;



long long INF = 1LL << 50;



bool shortest_path(int s);

//bool find_n_loop();



int main(){



	scanf("%d %d",&N,&M);



	for(int i=0;i<M;i++){

		int a,b;

		long long c;

		scanf("%d %d %lld",&a,&b,&c);

		struct edge e;

		e.from = a-1;

		e.to = b-1;

		e.cost = -1*c;

		es[i] = e;

	}





	if(shortest_path(0)){

		printf("inf\n");

	}else{

		//printf("%d\n",num[N-1]);



		printf("%lld\n",-d[N-1]);

	}

	/*

	for(int i=0;i<N;i++){

		printf("%lld\n",d[i]);

	}

	*/



	return 0;

}



//

bool shortest_path(int s){

	for(int i=0;i<N;i++) d[i] = INF;

	d[s] = 0;

	for(int j=0;j<N-1;j++){

		//bool update = false;

		for(int i=0;i<M;i++){

			edge e = es[i];

			if(d[e.from]!=INF && d[e.to] > d[e.from]+e.cost){

				d[e.to] = d[e.from]+e.cost;

				//update = true;

			}

		}

		//if(!update) break;

	}

	bool negative[1000];

	for (int i = 0; i < N; ++i) {

		negative[i] = false;

	}

	for (int loop = 0; loop < N; ++loop) {

		for (int i = 0; i < M; ++i) {

			edge e = es[i];

			if ((d[e.from] != INF && d[e.to] > d[e.from] + e.cost)) {

				d[e.to] = d[e.from] + e.cost;

				negative[e.to] = true;

			}

//			if (negative[e.from] == true) {

//					 negative[e.to] = true;

//			}

        }

    }

    return negative[N - 1];

}

//

/*

bool find_n_loop(){

	//for(int i=0;i<N;i++) d[i] = 0;



	for(int i=0;i<N;i++){

		for(int j=0;j<M;j++){

			edge e = es[j];

			if(d[e.to]>d[e.from]+e.cost){

				d[e.to] = d[e.from] + e.cost;

				if(i==N-1) return true;

			}

		}

	}

	return false;

}

*/
// Slower C++ solution:
#include<cstdio>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

typedef long long ll;

typedef pair<ll,int> pli;

#define fir first

#define sec second

#define Mp make_pair

const int MAXN = 2e5 + 5;



int a[MAXN];

ll lval[MAXN],rval[MAXN];



struct Edge

{

	int u,v;

	ll w;

};

inline bool cmp(const Edge &p,const Edge &q){ return p.w<q.w;}

vector<Edge> e;



int fa[MAXN];

inline void init(int n){ for(int i=1; i<=n; ++i) fa[i]=i;}

int find(int u){ return fa[u]==u? u: fa[u]=find(fa[u]);}

void connect(int u,int v){ fa[find(u)]=find(v);}



void gao(int l,int r)

{

	if(l==r) return;

	int mid = (l+r)>>1;

	

	ll lmn = lval[l];

	int lpos = l;

	for(int i=l; i<=mid; ++i)

		if(lmn > lval[i])

			lmn = lval[i], lpos = i;

	ll rmn = rval[r];

	int rpos = r;

	for(int i=mid+1; i<=r; ++i)

		if(rmn > rval[i])

			rmn = rval[i], rpos = i;

	

	for(int i=l; i<=mid; ++i)

		e.push_back((Edge){ i, rpos, lval[i] + rmn});

	for(int i=mid+1; i<=r; ++i)

		e.push_back((Edge){ lpos, i, lmn + rval[i]});

	

	gao(l,mid); gao(mid+1,r);

}



int main(void)

{

	int n;

	ll d;

	scanf("%d%lld",&n,&d);

	for(int i=1; i<=n; ++i) scanf("%d",&a[i]);

	

	for(int i=1; i<=n; ++i)

		lval[i] = a[i] - d*i,

		rval[i] = a[i] + d*i;

	

	gao(1,n);

	sort(e.begin(),e.end(),cmp);

	

	ll ans=0;

	init(n);

	for(int i=0; i<(int)e.size(); ++i)

	{

		int u=e[i].u, v=e[i].v;

		ll w=e[i].w;

		if(find(u) == find(v)) continue;

		ans += w;

		connect(u,v);

	}

	printf("%lld",ans);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.856506758963363x):
#include<cstdio>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

typedef long long ll;

typedef pair<ll,int> pli;

#define fir first

#define sec second

#define Mp make_pair

const int MAXN = 2e5 + 5;

const int inf = 0x3f3f3f3f;

const ll linf = 0x3f3f3f3f3f3f3f3f;



template<typename T>

void chk_min(T &a,T b){ if(a>b) a=b;}



ll a[MAXN];



int main(void)

{

	int n;	

	ll d;

	scanf("%d%lld",&n,&d);

	for(int i=1; i<=n; ++i) scanf("%lld",&a[i]);

	

	ll ans=0;

	for(int i=1; i<=n; ++i) ans += a[i];

	

	for(int i=2; i<=n; ++i) chk_min(a[i], a[i-1]+d);

	for(int i=n-1; i>=1; --i) chk_min(a[i], a[i+1]+d);

	

	for(int i=1; i<=n; ++i) ans += a[i];

	printf("%lld",ans + d*(n-1) - a[1] - a[n]);

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



ll BIT1[200010];

ll BIT2[200010];



void add1(int A, ll B) {

	while (A > 0) {

		BIT1[A] = min(BIT1[A], B);

		A -= A & -A;

	}

}

ll query1(int A) {

	ll kotae = 1e18;

	while (A <= 200000) {

		kotae = min(kotae, BIT1[A]);

		A += A & -A;

	}

	return kotae;

}

void add2(int A, ll B) {

	while (A <= 200000) {

		BIT2[A] = min(BIT2[A], B);

		A += A & -A;

	}

}

ll query2(int A) {

	ll kotae = 1e18;

	while (A > 0) {

		kotae = min(kotae, BIT2[A]);

		A -= A & -A;

	}

	return kotae;

}



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);





	ll N, D;

	cin >> N >> D;

	int A[200001];

	rep1(i, N) cin >> A[i];



	rep1(i, 200000) BIT1[i] = 1e18;

	rep1(i, 200000) BIT2[i] = 1e18;



	rep1(i, N) {

		add1(i, A[i] + i * D);

	}

	rep1(i, N) {

		add2(i, A[i] - i * D);

	}



	ll setuyaku = 0;

	for (int i = 2; i < N; i++) {

		ll kari1 = query1(i + 1) - i * D;

		ll kari2 = query2(i - 1) + i * D;

		if (A[i] > min(kari1, kari2)) {

			setuyaku += A[i] - min(kari1, kari2);

		}

	}



	ll motomoto = 0;

	rep1(i, N - 1) motomoto += A[i];

	rep1(i, N - 1) motomoto += A[i + 1];

	motomoto += (N - 1) * D;



	co(motomoto - setuyaku);



	Would you please return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.9798165537807795x):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);





	ll N, D;

	cin >> N >> D;

	int A[200001];

	ll C[200001];

	C[0] = 1e18;

	ll motomoto = (N - 1) * D;

	rep1(i, N) {

		cin >> A[i];

		motomoto += A[i];

		C[i] = min(C[i - 1], A[i] - i * D);

	}

	ll saishou = 1e18;

	ll setuyaku = 0;

	for (int i = N - 1; i > 1; i--) {

		saishou = min(saishou, A[i + 1] + (i + 1) * D);

		motomoto += A[i];

		ll kari = min(saishou - i * D, C[i - 1] + i * D);

		if (A[i] > kari) setuyaku += A[i] - kari;

	}

	co(motomoto - setuyaku);



	Would you please return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



ll BIT1[200010];

ll BIT2[200010];



void add1(int A, ll B) {

	while (A > 0) {

		BIT1[A] = min(BIT1[A], B);

		A -= A & -A;

	}

}

ll query1(int A) {

	ll kotae = 1e18;

	while (A <= 200000) {

		kotae = min(kotae, BIT1[A]);

		A += A & -A;

	}

	return kotae;

}

void add2(int A, ll B) {

	while (A <= 200000) {

		BIT2[A] = min(BIT2[A], B);

		A += A & -A;

	}

}

ll query2(int A) {

	ll kotae = 1e18;

	while (A > 0) {

		kotae = min(kotae, BIT2[A]);

		A -= A & -A;

	}

	return kotae;

}



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);





	ll N, D;

	cin >> N >> D;

	int A[200001];

	rep1(i, N) cin >> A[i];



	rep1(i, 200000) BIT1[i] = 1e18;

	rep1(i, 200000) BIT2[i] = 1e18;



	rep1(i, N) {

		add1(i, A[i] + i * D);

	}

	rep1(i, N) {

		add2(i, A[i] - i * D);

	}



	ll setuyaku = 0;

	for (int i = 2; i < N; i++) {

		ll kari1 = query1(i + 1) - i * D;

		ll kari2 = query2(i - 1) + i * D;

		if (A[i] > min(kari1, kari2)) {

			setuyaku += A[i] - min(kari1, kari2);

		}

	}



	ll motomoto = 0;

	rep1(i, N - 1) motomoto += A[i];

	rep1(i, N - 1) motomoto += A[i + 1];

	motomoto += (N - 1) * D;



	co(motomoto - setuyaku);



	Would you please return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.9916554561868858x):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



//getintとかいうのそんなに速いのかなテスト



int getint()

{

	char ch;

	while (!isdigit(ch = getchar()));

	int x = ch - 48;

	while (isdigit(ch = getchar())) x = x * 10 + ch - 48;

	return x;

}





int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);





	int N = getint();

	ll D = getint();

	ll kotae = (N - 1) * D;

	int A[200001];

	ll C[200001];

	C[0] = 1e18;

	rep1(i, N) {

		A[i] = getint();

		kotae += A[i];

		C[i] = min(C[i - 1] + D, (ll)A[i]);

	}

	ll mae = 1e18;

	for (int i = N - 1; i > 1; i--) {

		mae = min(mae + D, (ll)A[i + 1]);

		ll kari = min(mae, C[i - 1]) + D;

		kotae += min((ll)A[i], kari);

	}

	co(kotae);



	Would you please return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



ll BIT1[200010];

ll BIT2[200010];



void add1(int A, ll B) {

	while (A > 0) {

		BIT1[A] = min(BIT1[A], B);

		A -= A & -A;

	}

}

ll query1(int A) {

	ll kotae = 1e18;

	while (A <= 200000) {

		kotae = min(kotae, BIT1[A]);

		A += A & -A;

	}

	return kotae;

}

void add2(int A, ll B) {

	while (A <= 200000) {

		BIT2[A] = min(BIT2[A], B);

		A += A & -A;

	}

}

ll query2(int A) {

	ll kotae = 1e18;

	while (A > 0) {

		kotae = min(kotae, BIT2[A]);

		A -= A & -A;

	}

	return kotae;

}



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);





	ll N, D;

	cin >> N >> D;

	int A[200001];

	rep1(i, N) cin >> A[i];



	rep1(i, 200000) BIT1[i] = 1e18;

	rep1(i, 200000) BIT2[i] = 1e18;



	rep1(i, N) {

		add1(i, A[i] + i * D);

	}

	rep1(i, N) {

		add2(i, A[i] - i * D);

	}



	ll setuyaku = 0;

	for (int i = 2; i < N; i++) {

		ll kari1 = query1(i + 1) - i * D;

		ll kari2 = query2(i - 1) + i * D;

		if (A[i] > min(kari1, kari2)) {

			setuyaku += A[i] - min(kari1, kari2);

		}

	}



	ll motomoto = 0;

	rep1(i, N - 1) motomoto += A[i];

	rep1(i, N - 1) motomoto += A[i + 1];

	motomoto += (N - 1) * D;



	co(motomoto - setuyaku);



	Would you please return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.9924220210555292x):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define getchar getchar_unlocked

#define putchar putchar_unlocked

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



int getint() {

	char C;

	while (!isdigit(C = getchar()));

	int A = C - '0';

	while (isdigit(C = getchar())) A = A * 10 + C - '0';

	return A;

}



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);





	int N = getint();

	ll D = getint();

	ll kotae = (N - 1) * D;

	int A[200001];

	ll C[200001];

	C[0] = 1e18;

	rep1(i, N) {

		A[i] = getint();

		kotae += A[i];

		C[i] = min(C[i - 1] + D, (ll)A[i]);

	}

	ll mae = 1e18;

	for (int i = N - 1; i > 1; i--) {

		mae = min(mae + D, (ll)A[i + 1]);

		ll kari = min(mae, C[i - 1]) + D;

		kotae += min((ll)A[i], kari);

	}

	co(kotae);



	Would you please return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



ll BIT1[200010];

ll BIT2[200010];



void add1(int A, ll B) {

	while (A > 0) {

		BIT1[A] = min(BIT1[A], B);

		A -= A & -A;

	}

}

ll query1(int A) {

	ll kotae = 1e18;

	while (A <= 200000) {

		kotae = min(kotae, BIT1[A]);

		A += A & -A;

	}

	return kotae;

}

void add2(int A, ll B) {

	while (A <= 200000) {

		BIT2[A] = min(BIT2[A], B);

		A += A & -A;

	}

}

ll query2(int A) {

	ll kotae = 1e18;

	while (A > 0) {

		kotae = min(kotae, BIT2[A]);

		A -= A & -A;

	}

	return kotae;

}



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);





	ll N, D;

	cin >> N >> D;

	int A[200001];

	rep1(i, N) cin >> A[i];



	rep1(i, 200000) BIT1[i] = 1e18;

	rep1(i, 200000) BIT2[i] = 1e18;



	rep1(i, N) {

		add1(i, A[i] + i * D);

	}

	rep1(i, N) {

		add2(i, A[i] - i * D);

	}



	ll setuyaku = 0;

	for (int i = 2; i < N; i++) {

		ll kari1 = query1(i + 1) - i * D;

		ll kari2 = query2(i - 1) + i * D;

		if (A[i] > min(kari1, kari2)) {

			setuyaku += A[i] - min(kari1, kari2);

		}

	}



	ll motomoto = 0;

	rep1(i, N - 1) motomoto += A[i];

	rep1(i, N - 1) motomoto += A[i + 1];

	motomoto += (N - 1) * D;



	co(motomoto - setuyaku);



	Would you please return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.022134443281859x):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



const int cm = 1 << 17;

char cn[cm], *ci = cn + cm, ct;

inline char getcha() {

	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }

	return *ci++;

}

inline int getint() {

	int A = 0;

	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';

	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';

	return A;

}



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);





	int N = getint();

	ll D = getint();

	ll kotae = (N - 1) * D;

	int A[200001];

	ll C[200001];

	C[0] = 1e18;

	rep1(i, N) {

		A[i] = getint();

		kotae += A[i];

		C[i] = min(C[i - 1] + D, (ll)A[i]);

	}

	ll mae = 1e18;

	for (int i = N - 1; i > 1; i--) {

		mae = min(mae + D, (ll)A[i + 1]);

		ll kari = min(mae, C[i - 1]) + D;

		kotae += min((ll)A[i], kari);

	}

	co(kotae);



	Would you please return 0;

}
// Slower C++ solution:
// Code By H~S~C

#ifdef ONLINE_JUDGE

#pragma GCC optimize(1)

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize(4)

#pragma comment(linker, "/STACK:1024000000,1024000000")

#pragma GCC optimize("Os")

#pragma GCC optimize("Og")

#pragma GCC optimize("Ofast")

#pragma GCC target("avx,sse,sse2,sse3,ssse3,sse4")

#endif

#include <initializer_list>

#include <unordered_set>

#include <unordered_map>

#include <algorithm>

#include <iostream>

#include <utility>

#include <cstdlib>

#include <cstring>

#include <vector>

#include <cstdio>

#include <queue>

#include <stack>

#include <cmath>

#include <map>

#include <set>

#define pb push_back

#define rep(i,n) for (int i=0;i<(n);++i)

#define rep1(i,n) for (int i=1;i<=(n);++i)

#define Rep(i,a,b) for (int i=(a);i<=(b);++i)

#define All(a) a.begin(),a.end()

#define SZ(a) ((int)a.size())

#define sqr(s) ((s)*(s))

#define MP make_pair

#define fillset(a,val) memset(a,val,sizeof(a))

#define X first

#define Y second

#define endl '\n'

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

typedef pair <int,int> pii;

const int inf=0x3f3f3f3f;

const ll lnf=0x3f3f3f3f3f3f3f3f;

const double EPS=1e-9,PI=acos(-1.0);

const int mod1=1000000007,mod2=998244353;

//....................密..........封..........线..........下..........禁..........止..........hack...............................................

const int Maxn=200005;

ll n,d,a[Maxn],dpl[Maxn],dpr[Maxn],ans;

signed main()

{

	ios_base::sync_with_stdio(0);

	cin.tie(nullptr);cout.tie(nullptr);

	cin>>n>>d;rep(i,n) cin>>a[i],ans+=a[i];

	ans+=(n-1)*d;dpl[0]=a[0];dpr[n-1]=a[n-1];

	rep1(i,n-1) dpl[i]=min(a[i],dpl[i-1]+d);

	for (int i=n-2;~i;--i) dpr[i]=min(a[i],dpr[i+1]+d);

	rep1(i,n-2) ans+=min(dpl[i],dpr[i]);

	cout<<ans<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.376092243774095x):
#include <stdio.h>

inline char gc(){

	static char buf[100000],*p1=buf,*p2=buf;

	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

#define gc getchar

inline long long read(){

	long long now=0;int f=0;register char c=gc();

	for(;c<48||c>57;c=='-'&&(f=1),c=gc());for(;c>47&&c<58;now=(now<<3)+(now<<1)+c-'0',c=gc());

	return f?-now:now;

}

#define Maxn 200005

long long n,d,a[Maxn],dpl[Maxn],dpr[Maxn],ans;

long long Min(long long x, long long y) { return (((y - x) >> (64 - 1)) & (x ^ y)) ^ x; }

signed main()

{

	n=read(),d=read();

	for (int i=0;i<n;++i) a[i]=read(),ans+=a[i];

	ans+=(n-1)*d;dpl[0]=a[0];dpr[n-1]=a[n-1];

	for (int i=1;i<n;++i) dpl[i]=Min(a[i],dpl[i-1]+d);

	for (int i=n-2;~i;--i) dpr[i]=Min(a[i],dpr[i+1]+d);

	for (int i=1;i<n-1;++i) ans+=Min(dpl[i],dpr[i]);

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

	return 0;

}
// Slower C++ solution:
//https://atcoder.jp/contests/keyence2019/tasks/keyence2019_e 

#include <bits/stdc++.h>

using namespace std;

//#pragma GCC optimize("Ofast")

typedef long long ll;

typedef pair<ll, ll> pll;

typedef pair<int, int> pii;

typedef unsigned long long ull;

#define fst first

#define sed second

#define pb push_back

#define mp make_pair

#define rt register int

#define all(it) it.begin(), it.end()

#define rep(it, f, e) for (rt it = f; it <= e; ++it)

#define per(it, f, e) for (rt it = f; it >= e; --it)

const int MAXN = 2e5 + 10;

struct Dsu {

	int par[MAXN];

	Dsu() {

		rep (i, 1, MAXN - 1) {

			par[i] = i;

		}

	}

	inline int find(int x) {

		return x == par[x] ? x : par[x] = find(par[x]);

	}

	inline void mry(int a, int b) {

		par[find(a)] = find(b);

	}

	inline bool tog(int a, int b) {

		return find(a) == find(b);

	}

}	dsu;

ll A[MAXN], n, d;

vector<pair<ll,pii> > edge;

inline void solve(int l, int r) {

	if (l == r) return;

	int m = (l + r) >> 1;

	ll ml = 1e18, li = 0;

	rep (i, l, m) {

		if (ml > A[i] - i * d) {

			ml = A[i] - i * d;

			li = i;

		}

	}

	ll mr = 1e18, ri = 0;

	rep (i, m + 1, r) {

		if (mr > A[i] + i * d) {

			mr = A[i] + i * d;

			ri = i;

		}

	}

	rep (i, l, m) {

		edge.pb(mp(A[i] - i * d + mr,mp(i, ri)));

	}

	rep (i, m + 1, r) {

		edge.pb(mp(A[i] + i * d + ml,mp(i, li)));

	}

	solve(l, m);

	solve(m + 1, r);

}

int main() {

	cin >> n >> d;

	rep (i, 1, n) {

		cin >> A[i];

	}

	solve(1, n);

	sort(all(edge));

	ll ans = 0;

	for (auto e : edge) {

	//	cerr << e.sed.fst << ' ' << e.sed.sed <<endl;

		if (!dsu.tog(e.sed.fst, e.sed.sed)) {

			ans += e.fst;

			dsu.mry(e.sed.fst, e.sed.sed);

		}

	}

	cout << ans << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.7882986409516013x):
#include <bits/stdc++.h>

using namespace std;

//#pragma GCC optimize("Ofast")

typedef long long ll;

typedef pair<ll, ll> pll;

typedef pair<int, int> pii;

typedef unsigned long long ull;

#define fst first

#define sed second

#define pb push_back

#define mp make_pair

#define rt register int

#define all(it) it.begin(), it.end()

#define rep(it, f, e) for (rt it = f; it <= e; ++it)

#define per(it, f, e) for (rt it = f; it >= e; --it)

const int MAXN = 2e5 + 10;

int A[MAXN];

ll dpl[MAXN], dpr[MAXN];

int main() {

	ios::sync_with_stdio(false);

	cin.tie(NULL), cout.tie(NULL);

	int n, d;

	cin >> n >> d;

	ll ans = (n - 1ll) * d;

	rep (i, 1, n) {

		cin >> A[i];

		ans += A[i];

	}

	if (n == 1) {

		cout << 0 << endl;

		return 0;

	}

	dpl[1] = A[1];

	rep (i, 2, n) {

		dpl[i] = min((ll)A[i], dpl[i - 1] + d);

	}

	dpr[n] = A[n];

	per (i, n - 1, 1) {

		dpr[i] = min((ll)A[i], dpr[i + 1] + d);

	}

	rep (i, 2, n - 1) {

		ans += min(dpl[i], dpr[i]);

	}

	cout << ans <<endl;

	return 0;

}
// Slower C++ solution:
#include<vector>

#include<list>

#include<algorithm>

#include<iostream>

#include<string>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

using namespace std;

int main(){

  int i;

  int a[]={0,1,2,3,5,7,8,9},n;

  while(cin>>n&&n){

    for(i=0;pow(8,i)<=n;i++);

    for(i--;i>=0;i--){

      cout<<a[n/(int)pow(8,i)];

      n%=(int)pow(8,i);

    }

    cout<<endl;

  }

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.239887326306991x):
#include<cstdio>

int main(){

  int i;

  int a[11]={1},n;

  char s[9]="01235789";

  for(i=1;i<11;++i)

    a[i]=a[i-1]*8;

  while(scanf("%d",&n),n){

    for(i=0;a[i]<=n;++i);

    for(--i;i>=0;--i){

      printf("%c",s[n/a[i]]);

      n%=a[i];

    }

    puts("");

  }

  return 0;

}