#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;
long long b=0;
int idx=-1;
long long eval(int x){
return 1ll*m*x+b;
}
};
struct node{
int lc=-1,rc=-1;
bool ex=0;
line li;
}tn[mxn*20];
int cnt=0;
int create(){
cnt++;
tn[cnt].ex=0;
tn[cnt].lc=-1;
tn[cnt].rc=-1;
tn[cnt].li=line();
return cnt;
}
void upd(line li,int i=1,int l=0,int r=maxx){
int m=(l+r)/2;
auto&v=tn[i];
if(!v.ex){
v.li=li;
v.ex=1;
return;
}
if(li.eval(m)>v.li.eval(m))swap(li,v.li);
if(l==r)return;
if(li.eval(l)>v.li.eval(l)){
if(v.lc==-1)v.lc=create();
upd(li,v.lc,l,m);
}
else if(li.eval(r)>v.li.eval(r)){
if(v.rc==-1)v.rc=create();
upd(li,v.rc,m+1,r);
}
}
pair<long long,int>qry(int x,int i=1,int l=0,int r=maxx){
auto&v=tn[i];
pair<long long,int>res={-1,-1};
if(l>x||r<x)return res;
res=max(res,{v.li.eval(x),v.li.idx});
int m=(l+r)/2;
if(x<=m){
if(v.lc==-1)return res;
return max(res,qry(x,v.lc,l,m));
}
if(v.rc==-1)return res;
return max(res,qry(x,v.rc,m+1,r));
}
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 pr[n+1][k+1]={};
long long dp[n+1][2]={};
for(int j=1;j<=k;j++){
create();
for(int i=j+1;i<=n;i++){
upd(line{p[i-1],dp[i-1][0]-1ll*p[i-1]*p[i-1],i-1});
auto q=qry(p[i]);
dp[i][1]=q.F;
pr[i][j]=q.S;
dp[i-1][0]=dp[i-1][1];
}
dp[n][0]=dp[n][1];
// for(int i=j+1;i<=n;i++)dp[i][0]=dp[i][1];
cnt=0;
}
cout<<dp[n][0]<<'\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<<' ';
}
