#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
struct Line{
int n,k;
int eval(int x){return k*x+n;}
int ix;
};
deque<Line> st;
int ind;
const int INF=numeric_limits<int>::min();
int query(int x){
if(st.size()==0)return INF;
while(st.size()>1){
Line L=st.back();
st.pop_back();
if(L.eval(x)<=st.back().eval(x))continue;
st.push_back(L);
break;
}
ind=st.back().ix;
return st.back().eval(x);
}
void add(Line L){
if(st.empty()){
st.push_front(L);
return;
}
if(st.front().k==L.k){
if(st.front().n>=L.n)return;
else st.pop_front();
}
while(st.size()>=2){
Line x=st.front();
st.pop_front();
if((L.n-x.n)*(st.front().k-x.k)>=(x.n-st.front().n)*(x.k-L.k))continue;
st.push_front(x);
break;
}
st.push_front(L);
}
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);
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();
for(int i=1;i<n;i++){
ind=-1;
Line L;
L.k=-p[i-1];
L.n=dp0[i-1];
L.ix=i-1;
add(L);
dp1[i]=query(p[n-1]-p[i])+p[i]*(p[n-1]-p[i]);
pos[i][j]=ind;
}
//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;
}
