#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct line{
ll m,b,from;
// y=mx+b;
};
deque<line> dq;
bool check(line l1,line l2,line l3){
if(l1.m==l2.m and l1.b>=l2.b) return true;
if((l2.b-l3.b)*(l2.m-l1.m)<=(l1.b-l2.b)*(l3.m-l2.m)) return true;
return false;
}
void add(line l){
while(dq.size()>=2 and check(dq[dq.size()-2],dq[dq.size()-1],l)){
dq.pop_back();
}
dq.push_back(l);
}
pair<ll,ll> query(ll x){
while(dq.size()>=2 and dq[0].m*x+dq[0].b<=dq[1].m*x+dq[1].b){
dq.pop_front();
}
return {dq[0].m*x+dq[0].b,dq[0].from};
}
int main(){
ll n,k,i,j,q;
cin>>n>>k;
vector<ll> a(n+1),pre(n+2,0);
for(i=1 ; i<=n ; i++) cin>>a[i];
for(i=1 ; i<=n ; i++) pre[i]=pre[i-1]+a[i];
vector<ll> dp1(n+1),dp2(n+1);
vector<vector<int>> par(k+1,vector<int>(n+1));
for(i=1 ; i<=k ; i++){
dq.clear();
add({0,0,0});
for(j=1 ; j<=n ; j++){
// dp2[j]=dp1[q]+(pre[j]-pre[q])*pre[q]
// dp2[j]=pre[q]*pre[j]+dp1[q]-pre[q]^2
pair<ll,ll> val=query(pre[j]);
dp2[j]=val.first;
par[i][j]=val.second;
add({pre[j],dp1[j]-pre[j]*pre[j],j});
}
swap(dp2,dp1);
}
cout<<dp1[n]<<"\n";
ll u=n;
for(i=k ; i>=1 ; i--){
cout<<par[i][u]<<" ";
u=par[i][u];
}
return 0;
}
