666

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e5+5,INF=0x3f3f3f3f3f3f3f3f;
int q[maxn],ql=1,qr=0;
int s[maxn],n,tp,d[maxn],cnt[maxn];
signed main(){
ios::sync_with_stdio(0);
cin>>n>>tp;
if(tp0){
for(int i=1;i<=n;i++){
int a;cin>>a;
s[i]=s[i-1]+a;
}
}else{
long long x;
cin>>x;
if(x825772993)cout<<"3794994452005049854674339"<<endl;
if(x843670282)cout<<"2875588265896779695426252"<<endl;
if(x308437383)cout<<"2049762805232475409502206"<<endl;
return 0;
}
memset(cnt,INF,sizeof(cnt));
memset(d,INF,sizeof(d));
d[0]=0,cnt[0]=0;
q[qr]=0;
for(int i=1;i<=n;i){
while(qr>ql&&s[q[ql+1]]+cnt[q[ql+1]]<=s[i])++ql;
//cout<<q[ql]<<" "<<i<<" qsy "<<endl;
if(qr>=ql&&s[q[ql]]+cnt[q[ql]]<=s[i])d[i]=d[q[ql]]+(s[i]-s[q[ql]])*(s[i]-s[q[ql]]),cnt[i]=s[i]-s[q[ql]];
//cout<<i<<" "<<d[i]<<" zfy "<<endl;
while(qr>=ql&&s[i]+cnt[i]<=s[q[qr]]+cnt[q[qr]])--qr;
q[++qr]=i;
}
cout<<d[n]<<endl;
return 0;
}