#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
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 pb push_back
#define db double
#define pii pair<int,int>
#define fi first
#define se second
const int N=100010;
int n,k,a[N],tr[N][210],top;
ll s[N],f[N],p[N],g[N];
db lef[N];
int st[N];
vector<int> kq;
db giao(int u,int v)
{
return 1.0*(g[v]-g[u])/(s[v]-s[u]);
}
void add(int i,int j)
{
if(top>=0&&s[i-1]==s[st[top]]) --top;
while(top>=1&&lef[top]<=giao(i-1,st[top])) --top;
st[++top]=i-1;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=-1;
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]=-p[i]*s[st[o]]+g[st[o]]+p[i]*s[i];
tr[i][j]=st[o];
}
forinc(i,j,n-1) g[i]=f[i];
}
int I=0,J=k;
forinc(i,k,n-1) if(f[i]>=f[I]) I=i;
cout<<f[I]<<"\n";
while(J)
{
kq.pb(I);
I=tr[I][J],J--;
}
reverse(kq.begin(),kq.end());
forv(x,kq) cout<<x<<" ";
}
