#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define int long long
#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 pb push_back
#define db double
#define pii pair<int,int>
#define fi first
#define se second
#define piii pair<int,pii>
#define sf se.fi
#define ss se.se
const int N=100010;
int f[N][210],n,k,a[N],s[N],p[N],tr[N][210],top;
db lef[N];
piii st[N];
vector<int> kq;
db giao(piii u,piii v)
{
return 1.0*(v.ss-u.ss)/(u.sf-v.sf);
}
void add(int i,int j)
{
if(i==1&&j!=1) return;
piii O={i-1,{-s[i-1],f[i-1][j-1]}};
if(top>=0&&O.sf==st[top].sf) --top;
while(top>=1&&lef[top]<=giao(O,st[top])) --top;
st[++top]=O;lef[top]=giao(st[top],st[top-1]);
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("sequence.inp","r",stdin);
cin>>n>>k;
forinc(i,1,n) cin>>a[i],s[i]=s[i-1]+a[i];
forinc(i,1,n) p[i]=s[n]-s[i];
forinc(j,1,k)
{
top=0;
forinc(i,j,n-1)
{
add(i,j);
int l=1,r=top,o=0;
while(l<=r)
{
int mid=(l+r)/2;
if(lef[mid]>p[i]) o=mid,l=mid+1;
else r=mid-1;
}
f[i][j]=p[i]*st[o].sf+st[o].ss+p[i]*s[i];
tr[i][j]=st[o].fi;
}
}
int I=0,J=k;
forinc(i,k,n-1) if(f[i][k]>=f[I][k]) I=i;
cout<<f[I][J]<<"\n";
while(J)
{
kq.pb(I);
I=tr[I][J],J--;
}
reverse(kq.begin(),kq.end());
forv(x,kq) cout<<x<<" ";
}
