#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fir first
#define sec second
#define pb push_back
#pragma GCC optimize("O3,unroll-loops")
const int maxn=1e5;
int n,k,a[maxn+2];
long long pref[maxn+2];
long long dp[2][maxn+2];
int opt[202][maxn+2];
void dnc(int lvl,int l,int r,int optl,int optr){
if(l>r)return;
int mid=(l+r)/2;
int cur=lvl%2,prv=1-cur;
dp[cur][mid]=-1e18;
int op=-1,hmm=pref[n]-pref[mid];
long long mx=-1e18;
for(int q=optl;q<=min(optr,mid-1);q++){
long long tot=dp[prv][q]+1LL*(pref[mid]-pref[q])*hmm;
if(mx<tot){
mx=tot;
op=q;
}
}
opt[lvl][mid]=op; dp[cur][mid]=mx;
dnc(lvl,l,mid-1,optl,op);
dnc(lvl,mid+1,r,op,optr);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>k; k++;
for(int q=1;q<=n;q++){
cin>>a[q];
pref[q]=pref[q-1]+a[q];
dp[0][q]=-1e18;
}
dp[0][0]=0;
for(int q=1;q<=k;q++){
dnc(q,q,n,q-1,n);
}
//cout<<dp[7][2]<<endl;
cout<<dp[k%2][n]<<'\n';
for(int q=k;q>1;q--){
cout<<opt[q][n]<<' ';
n=opt[q][n];
}
}
