#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back #define int ll using namespace std; typedef long long ll; const int maxn=2e5+10; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; }int n,c,a[maxn],lst[maxn],nxt[maxn]; struct node { int val,pos,len; ll s1; node(int _val,int _pos,int _len,ll _s1){val=_val,pos=_pos,len=_len,s1=_s1;} node(){} }T[maxn]; node operator+(node a,node b){ return T[a.pos]=node(max(a.val,b.val),a.pos,a.len+b.len,a.s1+b.s1); } set<node>s; bool operator<(node a,node b){return a.val<b.val;} pair<ll,int> gmin(ll a,ll b,ll c,ll d,ll e){ //cout<<"test "<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<e<<"\n"; ll val=-b/(2*a),res=a*d*d+b*d+c; for(ll i=val-3;i<=val+3;++i)if(i>=d&&i<=e)res=min(res,a*i*i+b*i+c); res=min(res,a*e*e+b*e+c);bool tag=(a*e*e+b*e+c==res); //cout<<"test "<<res<<" "<<tag<<"\n"; return m_p(res,tag); } void slv(){ n=read(),c=read();up(i,1,n)a[i]=read(); up(i,2,n)lst[i]=i-1;up(i,1,n-1)nxt[i]=i+1; ll res=0;up(i,1,n)s.insert(T[i]=node(a[i],i,1,a[i])); while(s.size()>1){ auto it=*s.begin();s.erase(it); //cerr<<"? "<<it.pos<<"\n"; int a=lst[it.pos],b=nxt[it.pos],mn=1e9; bool flg=0; if(a)mn=min(mn,T[a].val),flg|=(T[a].val<it.val);if(b)mn=min(mn,T[b].val),flg|=(T[b].val<it.val); //cerr<<"? "<<a<<" "<<b<<"\n"; if(flg){ int mx=max(T[a].val,T[b].val); res+=(mx-it.val)*1ll*c; continue; }if(mn==int(1e9))continue; //printf("? %lld %d %d\n",it.s2,c,mn); auto jt=gmin(it.len,-2*it.s1-c,-it.val*1ll*it.val*1ll*it.len+it.val*2ll*it.s1+c*mn,it.val,mn); //cout<<"? "<<it.pos<<" "<<jt.p1<<" "<<jt.p2<<"\n"; //cout<<"add "<<it.pos<<" "<<jt.p1<<" "<<jt.p2<<"\n"; if(!jt.p2){ res+=jt.p1;continue; }res+=jt.p1; if(T[a].val==mn){ nxt[a]=b,lst[b]=a;s.erase(T[a]); s.insert(T[a]+it); }else { nxt[a]=b,lst[b]=a;s.erase(T[b]); s.insert(T[b]+it); } }cout<<res; }signed main(){ //freopen("seq.in","r",stdin); //freopen("seq.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }