#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define rev( x ) reverse( x .begin(), x .end())
ll dp[1000007],dppop[1000007];
int pop[1000007][207];
ll n,k,a,b,c,s,s2;
vector<ll>v={0};
deque<pair<pii,ll>>hull;
ll eval(pair<ll,ll>f,ll x){
return f.ff*x+f.ss;
}
void add(pair<pair<ll,ll>,ll> pr){
if(hull.size() && hull.back().ff==pr.ff){hull.back()=pr;return;}
hull.pb(pr);
while(hull.size()>=3){
auto p3=hull.back();
hull.pop_back();
auto p2=hull.back();
hull.pop_back();
auto p1=hull.back();
ll pom=p3.ff.ss-p1.ff.ss;
ll pom2=p1.ff.ff-p3.ff.ff;
if(eval(p2.ff,pom/pom2)>=eval(p1.ff,pom/pom2) && eval(p2.ff,pom/pom2+1)>=eval(p3.ff,pom/pom2+1)){
hull.pb(p3);
}
else{
hull.pb(p2);hull.pb(p3);break;
}
}
}
pii bst(ll x){
while(hull.size()>=2){
auto p1=hull.front();
hull.pop_front();
auto p2=hull.front();
if(eval(p1.ff,x)<eval(p2.ff,x)){
hull.push_front(p1);
break;
}
}
return {eval(hull.front().ff,x),hull.front().ss};
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>k;
k++;
for(ll i=0;i<n;i++){
cin>>a;
s+=a*a;
s2+=a;
v.pb(v.back()+a);
}
for(ll i=1;i<=n;i++)dppop[i]=INFL;
for(ll i=1;i<=k;i++){
if(i==1)
add({{0,0},0});
else
add({{0,INFL},0});
for(ll j=1;j<=n;j++){
pii pom=bst(v[j]);
pom.ff+=v[j]*v[j];
dp[j]=pom.ff;
//cout<<dp[j]<<" "<<bst(v[j]).ff<<" "<<bst(v[j]).ss<<" "<<v[j]<<" ";
pop[j][i]=pom.ss;
add({{-2*v[j],dppop[j]+v[j]*v[j]},j});
//cout<<dppop[j]+v[j]*v[j]<<" "<<-2*v[j]<<" "<<flush;
}
//cout<<"\n"<<flush;
swap(dp,dppop);
hull.clear();
}
cout<<(s2*s2-dppop[n])/2<<"\n";
vector<ll> ans;
ll ak=n;
while(ak!=0){
ans.pb(ak);
ak=pop[ak][k];
k--;
}
rev(ans);
ans.pop_back();
for(ll i : ans)cout<<i<<" ";
}
