text: # Problem There are N cities in Republic of AtCoder.The size of the i-th city is A_{i}.Takahashi would like to build N-1 bidirectional roads connecting two cities so that any city can be reached from any other city by using these roads.Assume that the cost of building a road connecting the i-th city and the j-th city is |i-j| \times D + A_{i} + A_{j}.For Takahashi, find the minimum possible total cost to achieve the objective.Constraints * 1 \leq N \leq 2 \times 10^5 * 1 \leq D \leq 10^9 * 1 \leq A_{i} \leq 10^9 * A_{i} and D are integers.Input Input is given from Standard Input in the following format: N D A_1 A_2 ...A_N Output Print the minimum possible total cost.Examples Input 3 1 1 100 1 Output 106 Input 3 1000 1 100 1 Output 2202 Input 6 14 25 171 7 1 17 162 Output 497 Input 12 5 43 94 27 3 69 99 56 25 8 15 46 8 Output 658 # Solution #include<bits/stdc++.h> #define ll long long using namespace std; struct node { int u,v; ll w; bool operator<(const node &o)const{return w<o.w;} }e[6000005]; int n,cot=0,a[200005],fail[200005]; ll d; void add(int l,int r) { if(l>=r) return; int m=l+r>>1; ll mi=1e18,pos; for(int i=l;i<=m;i++) { ll f=a[i]-d*i; if(f<mi) mi=f,pos=i; } for(int i=m+1;i<=r;i++) e[cot].u=pos,e[cot].v=i,e[cot++].w=a[i]+a[pos]+d*(i-pos); mi=1e18; for(int i=m+1;i<=r;i++) { ll f=a[i]+d*i; if(f<mi) mi=f,pos=i; } for(int i=l;i<=m;i++) e[cot].u=i,e[cot].v=pos,e[cot++].w=a[i]+a[pos]+d*(pos-i); add(l,m);add(m+1,r); } int get_fa(int x) { return fail[x]==x?x:fail[x]=get_fa(fail[x]); } ll kruskal() { sort(e,e+cot); for(int i=1;i<=200000;i++) fail[i]=i; ll ans=0; for(int i=0;i<cot;i++) { int fu=get_fa(e[i].u),fv=get_fa(e[i].v); if(fu==fv) continue; fail[fu]=fv; ans+=e[i].w; } return ans; } int main() { scanf("%d%lld",&n,&d); for(int i=1;i<=n;i++) scanf("%d",&a[i]); add(1,n); printf("%lld\n",kruskal()); }