#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const long long INF=1e18;
long long dp[MAXN][2],pref[MAXN];
int trace[MAXN][222];
void dnc(int l,int r,int pl,int pr,int c)
{
if(l>r) return ;
int pos=0,mid=(l+r)/2;
for(int i=pl;i<=pr&&i<=mid;i++) if(dp[mid][c%2]<dp[i-1][1-c%2]+pref[i-1]*(pref[mid]-pref[i-1]))
dp[mid][c%2]=dp[i-1][1-c%2]+pref[i-1]*(pref[mid]-pref[i-1]),pos=i;
trace[mid][c]=pos-1;
if(l==r) return ;
dnc(l,mid-1,pl,pos,c);
dnc(mid+1,r,pos,pr,c);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
int res;
cin>>res;
pref[i]=pref[i-1]+res;
}
for(int i=0;i<=n;i++) dp[i][0]=dp[i][1]=-INF;
dp[0][0]=0;
for(int i=1;i<=k+1;i++)
{
for(int j=1;j<=n;j++) dp[j][i%2]=-INF;
dnc(i,n,i-1,n,i);
}
cout<<dp[n][1-k%2]<<"\n";
int pos=n;
for(int i=k+1;i>1;i--) cout<<(pos=trace[pos][i])<<" ";
}
