#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
ll dp[2][N],arr[N],sum[N];
int ind[205][N];
struct CHT{
struct line{
ll m,c;
double cut(line b){return (double)(b.c-c)/(double)(m-b.m);}
ll val(ll x){return m*x+c;};
};
deque<pair<line,int>> hull;
bool bad(line a,line b,line c){return c.cut(b)<=c.cut(a);}
void ins(ll m,ll c,int i){
line l={m,c};
while(hull.size()>=2 && bad(hull.end()[-2].first,hull.back().first,l)) hull.pop_back();
hull.push_back({l,i});
}
pair<ll,int> query(ll x){
while(hull.size()>=2 && hull[0].first.val(x)<=hull[1].first.val(x)) hull.pop_front();
return {hull[0].first.val(x),hull[0].second};
}
void clr(){while(!hull.empty()) hull.pop_back();}
}hode;
int main(){
int n,k;
cin>>n >>k;
for(int i=1;i<=n;i++) cin>>arr[i];
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+arr[i];
for(int i=1;i<=k+1;i++){
int now=i&1;
int pre=(i+1)&1;
hode.ins(0,0,0);
for(int j=1;j<=n;j++){
pair<ll,int> ret=hode.query(sum[j]);
if(i!=1) ind[i][j]=ret.second;
dp[now][j]=sum[j]*(sum[n]-sum[j])+ret.first;
if(i!=1) hode.ins(sum[j],dp[pre][j]-sum[j]*sum[n],j);
}
hode.clr();
}
cout<<dp[(k+1)&1][n] <<"\n";
vector<int> ans;
int now=n;
for(int i=k+1;i>=2;i--){
now=ind[i][now];
ans.push_back(now);
}
reverse(ans.begin(),ans.end());
for(auto tmp:ans) cout<<tmp <<" ";
}
