#include<bits/stdc++.h> #define Rf(i,a,b) for(int i=(a);i<=(b);i++) #define Rb(i,a,b) for(int i=(a);i>=(b);i--) #define ll long long #define PII pair<int,int> #define mpx make_pair #define int ll using namespace std; const int S=1e7+10,N=1e5+10,V=120; int n,c;int a[N];int v=0; struct nd{ int id,vl; bool operator<(const nd &b){ return vl<b.vl; } }tmp[N]; int fa[N],val[N];ll w[N];int len[N]; int find(int x){ if(x==fa[x]) return x; return fa[x]=find(fa[x]); } void merge(int x,int y){ int X=find(x),Y=find(y);//cout<<X<<' '<<Y<<"I"<<endl; fa[X]=Y;len[Y]+=len[X];w[Y]+=w[X]; } signed main(){ cin>>n>>c;Rf(i,1,n) cin>>a[i],fa[i]=i,w[i]=1,len[i]=1; Rf(i,1,n) tmp[i]=(nd){i,a[i]},val[i]=a[i];sort(tmp+1,tmp+n+1); ll ans=0;Rf(i,2,n) ans+=1ll*abs(a[i]-a[i-1])*c/*,cout<<ans<<' '*/;//cout<<ans<<endl; Rf(i,2,n) if(val[i]==val[i-1]) merge(i,i-1); Rf(i,1,n){ int ps=tmp[i].id; int lp=find(ps)-1,rp=find(ps)+len[find(ps)]; int to=1e9+10;int cnt=0;//cout<<ps<<' '<<lp<<' '<<rp<<endl;cout<<find(ps)<<endl; if(lp>=1){ to=min(to,val[find(lp)]);cnt++; }if(rp<=n){ to=min(to,val[find(rp)]);cnt++; }if(to>1e6+30) break;;//cout<<to<<' '<<cnt<<' '<<i<<' '<<w[find(ps)]<<endl; int now=val[find(ps)];if(to<now) continue; int cost=cnt*c;if(w[find(ps)]<=cnt*c){ int cntlen=(cost-w[find(ps)])/len[find(ps)]; cntlen=cntlen/2*2;int D=cntlen/2; //cout<<cost<<' '<<cntlen<<endl; D=min(to-now,D+1); //cout<<D<<endl; ll pay=(D)*w[find(ps)]+(D*2)/2*(D-1)*len[find(ps)]-cost*D;//cout<<pay<<' '<<w[find(ps)]<<' '; ans+=pay; val[find(ps)]+=D;w[find(ps)]+=2*D*len[find(ps)];//cout<<cost<<endl; } if(lp>=1){ if(val[find(ps)]==val[find(lp)]) merge(ps,lp); }//Rf(i,1,n) cout<<len[i]<<' ';cout<<endl; if(rp<=n){ //cout<<val[find(ps)]<<' '<<val[find(lp)]<<endl; if(val[find(ps)]==val[find(rp)]) merge(rp,ps); }//Rf(i,1,n) cout<<len[i]<<' ';cout<<endl; //cout<<ans<<endl; }cout<<ans; return 0; }