#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,dp[100003][202],k,jm[100003],f[100009],K1,B1,K2,B2,K3,B3,x,nxt[100003][202],p[100009],pi;
deque <pair <long long, long long> > de;
deque <long long> I;
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>b;
for(i=1; i<=a; i++){
cin>>f[i];
jm[i]=jm[i-1]+f[i];
//de.push_back(jm[i],-jm[i]*jm[i]);
}
for(i=1; i<=a; i++){
dp[i][0]=0;
}
for(k=1; k<=b; k++){
de.clear();I.clear();
de.push_back(make_pair(jm[k],dp[k][k-1]-jm[k]*jm[k]));
I.push_back(k);
for(i=k+1; i<=a; i++){
x=jm[i];
while(de.size()>=2){
K1=de[0].first;B1=de[0].second;
K2=de[1].first;B2=de[1].second;
if(K2*x+B2>=K1*x+B1){
de.pop_front();
I.pop_front();
}else{
break;
}
}
dp[i][k]=de[0].first*x+de[0].second;
nxt[i][k]=I.front();
K3=jm[i];B3=dp[i][k-1]-jm[i]*jm[i];
while(de.size()>=1){
K1=de.back().first;B1=de.back().second;
if(K1<=K3&&B1<=B3){
de.pop_back();
I.pop_back();
}else{
break;
}
}
while(de.size()>=2){
K2=de[de.size()-1].first;B2=de[de.size()-1].second;
K1=de[de.size()-2].first;B1=de[de.size()-2].second;
/*if(K1==K2){
de.pop_back();
I.pop_back();
continue;
}*/
if((B2-B3)*(K2-K1)<=(B1-B2)*(K3-K2)){
de.pop_back();
I.pop_back();
}else{
break;
}
}
if(de.size()>=1){
K1=de.back().first;B1=de.back().second;
if(K1==K3){
continue;
}
}
de.push_back(make_pair(jm[i],dp[i][k-1]-jm[i]*jm[i]));
I.push_back(i);
}
}
cout<<dp[a][b]<<endl;
pi=0;
c=a;
for(j=b; j>=1; j--){
c=nxt[c][j];
pi++;
p[pi]=c;
}
for(i=pi; i>=1; i--) cout<<p[i]<<" ";
return 0;
}
