#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[maxn+2][2];
int opt[maxn+2][202];
void dnc(int lvl,int l,int r,int optl,int optr){
if(l>r)return;
int mid=(l+r)/2;
dp[mid][lvl%2]=-1e18;
int op=-1;
long long mx=-1e18;
for(int q=optl;q<=min(optr,mid-1);q++){
long long tot=dp[q][(lvl-1)%2]+1LL*(pref[mid]-pref[q])*(pref[n]-pref[mid]);
if(mx<tot){
mx=tot;
op=q;
}
}
opt[mid][lvl]=op; dp[mid][lvl%2]=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[q][0]=-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[n][k%2]<<'\n';
for(int q=k;q>1;q--){
cout<<opt[n][q]<<' ';
n=opt[n][q];
}
}
