#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) (int)x.size()
using namespace std;
const int mxn=2e5+5;
ll a[mxn]{0};
ll dpf[mxn]{0},dps[mxn]{0};
int pr[202][mxn]{0};
int cur=1,n;
void solve(int l,int r,int opl,int opr){
if(l>r)return;
int m=(l+r)>>1;
pll t={-1e16,-1e16};
for(int i=opl;i<=min(m-1,opr);i++){
t=max(t,{dpf[i]+(a[n]-a[m])*(a[m]-a[i]),i});
}dps[m]=t.f;pr[cur][m]=t.s;
if(l==r)return;
solve(l,m-1,opl,t.s);
solve(m+1,r,t.s,opr);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int k;cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];
for(int i=1;i<=n;i++)dpf[i]=(a[i])*(a[n]-a[i]);
for(int i=2;i<=k;i++){
solve(i,n,i-1,n);
for(int j=1;j<=n;j++)dpf[j]=dps[j];
cur++;
}ll ans=-1,mem=-1;
for(int i=1;i<=n;i++){
if(dpf[i]>ans){
ans=dpf[i];
mem=i;
}
}
cout<<ans<<'\n';stack<int>st;st.push(mem);
for(int i=cur-1;i>=1;i--){
st.push(pr[i][mem]);mem=pr[i][mem];
}while(!st.empty()){
cout<<st.top()<<' ';st.pop();
}
}
