#include"bits/stdc++.h"
using namespace std;
#define int long long
#define S second
#define F first
const int maxx=1e9+5;
const int mxn=1e5+5;
const int mxk=2e2+5;
struct line{
int m=1,b=0;
int eval(int x){
return m*x+b;
}
};
struct node{
node *le=nullptr;
node *ri=nullptr;
line *l=nullptr;
int idx=-1;
};
node* root=new node();
void upd(line* l,int idx,node* v,int le,int ri){
int m=(le+ri)/2;
if(!v->l){
v->l=l;
v->idx=idx;
return;
}
if(l->eval(m)>v->l->eval(m))swap(l,v->l),swap(idx,v->idx);
if(le==ri)return;
if(l->eval(le)>v->l->eval(le)){
if(!v->le)v->le=new node();
upd(l,idx,v->le,le,m);
}
else if(l->eval(ri)>v->l->eval(ri)){
if(!v->ri)v->ri=new node();
upd(l,idx,v->ri,m+1,ri);
}
}
pair<int,int>qry(int x,node* v,int l,int r){
pair<int,int>res={-1,-1};
if(l>x||r<x||!v||!v->l)return res;
res=max(res,{v->l->eval(x),v->idx});
int m=(l+r)/2;
if(x<=m)return max(res,qry(x,v->le,l,m));
else return max(res,qry(x,v->ri,m+1,r));
}
void clr(node* v=root){
if(!v)return;
clr(v->le);
clr(v->ri);
// delete v;
v=nullptr;
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int n,k;
cin>>n>>k;
int a[n+1],p[n+1]={};
for(int i=1;i<=n;i++){
cin>>a[i];
p[i]=p[i-1]+a[i];
}
int dp[n+1][k+1]={},pr[n+1][k+1]={};
for(int j=1;j<=k;j++){
for(int i=j;i<=n;i++){
upd(new line{p[i],dp[i][j-1]-p[i]*p[i]},i,root,0,maxx);
}
for(int i=j+1;i<=n;i++){
auto q=qry(p[i],root,0,maxx);
dp[i][j]=q.F;
pr[i][j]=q.S;
}
clr();
}
cout<<dp[n][k]<<'\n';
vector<int>v;
while(k){
v.push_back(pr[n][k]);
n=pr[n][k];
k--;
}
sort(v.begin(),v.end());
for(int i:v)cout<<i<<' ';
}
