#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
const int MN = 100100;
const int MK = 222;
const ll INFL = 1e18;
vl w,pr;
ll dp[2][MN];
int pd[MK][MN];
void ds(ll ro, ll l, ll r, ll kl, ll kr) {
if(l > r) {return;}
ll m = (l+r)/2;
ll mo = kl;
ll mv = -1;
for(int i=kl;i<=min(m-1,kr);i++) {
ll pk = dp[(ro&1)^1][i] + pr[i]*(pr[m]-pr[i]);
if(pk > mv) {mv = pk;mo = i;}
}
dp[ro&1][m] = mv;
pd[ro][m] = mo;
ds(ro,l,m-1,kl,mo);
ds(ro,m+1,r,mo,kr);
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);
memset(dp,0,sizeof(dp));
int n,k;
cin >> n >> k;
pr.push_back(0);
for(int i=0;i<n;i++) {
ll t;
cin >> t;
w.push_back(t);
pr.push_back(pr.back()+t);
}
for(int i=1;i<=k;i++) {
ds(i,i+1,n,i,n);
}
vl res;
ll bak = n;
for(int i=k;i>0;i--) {
res.push_back(pd[i][bak]);
bak = res.back();
}
cout << dp[k&1][n] << '\n';
reverse(res.begin(),res.end());
for(int i=0;i<k;i++) {
if(i > 0) {cout << " ";}
cout << res[i];
}
cout << '\n';
}
