#include <bits/stdc++.h>
using namespace std;
#define forinc(a, b, c) for(int a=b, _c=c; a<=_c; ++a)
#define fordec(a, b, c) for(int a=b, _c=c; a>=_c; --a)
#define forv(a, b) for(auto &a : b)
#define rep(i, n) forinc(i, 1, n)
#define repv(i, n) forinc(i, 0, n - 1)
#define ii pair<int,int>
#define fi first
#define se second
#define all(a) begin(a), end(a)
#define reset(f, x) memset(f, x, sizeof(f))
#define eb emplace_back
#define pb push_back
const int N=1e5+5;
long long n,a[N];
long long f[2][N];
int k;
int pre[202][N];
int top;
long long s[N],x[N];
struct line{long long x,y;int id;} li[N];
double q[N];
double G(line x,line y){return 1.0*(x.y-y.y)/(y.x-x.x);}
bool ok(line p){
if(p.x==li[top].x) return false;
if(top==1) return 1;
double x1=G(p,li[top]);
double x2=G(p,li[top-1]);
return x1>x2;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
if(fopen("input.txt", "r")) freopen("input.txt", "r", stdin);
cin>>n>>k;
forinc(i,1,n) cin>>a[i], s[i]=s[i-1]+a[i];
fordec(i,n,1) x[i]=x[i+1]+a[i];
forinc(i,1,k){
int u=i&1;
top=0;
li[++top]={s[i-1],f[u^1][i-1],i-1};
q[top]=-1e15;
forinc(j,i,n-1){
int l=1, r=top, z=0;
while(l<=r) {
int mid=l+(r-l)/2;
if(q[mid]<=-x[j+1]) z=mid, l=mid+1;
else r=mid-1;
}
f[u][j]=s[j]*x[j+1]-li[z].x*x[j+1]+li[z].y;
pre[i][j]=li[z].id;
line uu;
uu.x=s[j], uu.y=f[u^1][j], uu.id=j;
if(uu.x==li[top].x && uu.y>=li[top].y) continue;
while(top && !ok(uu)) top--;
li[++top]=uu;
if(top>1) q[top]=G(li[top],li[top-1]);
}
}
int now=0;
forinc(i,1,n-1) if(f[k&1][now]<=f[k&1][i]) now=i;
cout<<f[k&1][now]<<'\n';
vector<int> ans; ans.pb(now);
fordec(i,k,2) ans.pb(pre[i][now]), now=pre[i][now];
reverse(all(ans));
forv(v, ans) cout<<v<<' ';
}
