#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
struct Line{
bool act=false;
int n,k;
int eval(int x){return k*x+n;}
int ix;
};
vector<Line> st;
vector<int> b;
int ind;
const int INF=numeric_limits<int>::min();
void add(int node, int l, int r, Line L){
if(!st[node].act){
st[node]=L;
return;
}
int rold=st[node].eval(b[r]), rnew=L.eval(b[r]);
int lold=st[node].eval(b[l]), lnew=L.eval(b[l]);
if(lold>=lnew && rold>=rnew)return;
if(lold<lnew && rold<rnew){
st[node]=L;
return;
}
if(lold<lnew)swap(L,st[node]);
int mid=(l+r)/2;
if(L.eval(b[mid])<=st[node].eval(b[mid])){
add(node*2+1,mid+1,r,L);
return;
}
else{
add(node*2,l,mid,st[node]);
st[node]=L;
return;
}
}
int query(int node, int l, int r, int x){
if(!st[node].act)return INF;
if(l==r){ind=st[node].ix;return st[node].eval(x);}
int mid=(l+r)/2;
int sol=st[node].eval(x);
ind=st[node].ix;
if(x<=b[mid]){
int ans=query(node*2,l,mid,x);
if(ans<=sol)ind=st[node].ix;
sol=max(sol,ans);
}
else{
int ans=query(node*2+1,mid+1,r,x);
if(ans<=sol)ind=st[node].ix;
sol=max(sol,ans);
}
return sol;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,k;
cin>>n>>k;
vector<int> v(n);
for(int i=0;i<n;i++)cin>>v[i];
vector<int> p(n);
p[0]=v[0];
for(int i=1;i<n;i++)p[i]=p[i-1]+v[i];
vector<int> dp0(n,0);
vector<int> dp1(n,0);
// for(int l=0;l<n;l++)cout<<p[l]<<' ';
// cout<<endl;
vector<vector<int32_t>> pos(n);
for(int i=0;i<n;i++)pos[i].assign(k+2,-1);
b.resize(n);
for(int i=0;i<n;i++)b[i]=p[n-1]-p[n-1-i];
for(int i=0;i<n;i++)dp0[i]=p[i]*(p[n-1]-p[i]);
//for(int l=0;l<n;l++)cout<<dp0[l]<<' ';
// cout<<endl;
for(int j=2;j<=k+1;j++){
st.clear();
st.resize(4*n);
for(int i=1;i<n;i++){
ind=-1;
Line L;
L.act=true;
L.k=-p[i-1];
L.n=dp0[i-1];
L.ix=i-1;
add(1,0,n-1,L);
dp1[i]=query(1,0,n-1,p[n-1]-p[i])+p[i]*(p[n-1]-p[i]);
pos[i][j]=ind;//cout<<1<<endl;
}
//for(int l=0;l<n;l++)cout<<dp1[l]<<' ';
//cout<<endl;
for(int l=0;l<n;l++)dp0[l]=dp1[l];
}
cout<<dp0[n-1]<<endl;
//for(int i=0;i<=k+1;i++){
// for(int j=0;j<n;j++)cout<<pos[j][i]<<' ';
// cout<<endl;
// }
int tr=n-1;
for(int i=k+1;i>1;i--){
cout<<pos[tr][i]+1<<' ';
tr=pos[tr][i];
}
return 0;
}
