#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15;
#define int long long
int a[N];
int b[N];
int n, k;
int dp[N][215];
int pre[N];
int nm;
int w[N];
int x[N];
int tv[N][215];
int id = 0;
int cost(int l, int r){
return (pre[r] - pre[l-1]) * (pre[n] - pre[r]);
}
void cal(int k, int l, int r, int opl, int opr) {
if (l > r) return;
int mid = (l + r) / 2;
int opm = -1;
dp[mid][k] = -1e18;
for (int i = min(opr,mid); i >= opl; i--) {
int val = dp[i][k-1] + cost(i+1,mid);
if (val > dp[mid][k]) {
dp[mid][k] = val;
opm = i;
}
}
tv[mid][id] = opm;
// cout << mid << " " << id << " " << opm << endl;
cal(k, l, mid - 1, opl, opm);
cal(k, mid + 1, r, opm, opr);
}
signed main() {
ios_base::sync_with_stdio();
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
pre[i] = pre[i-1] + a[i];
}
for (int i = 1; i <= n; i++) dp[i][1] = cost(1,i);
for (int i = 2; i <= k; i++) {
id++;
cal(i, 1, n, 1, n);
// for (int j = 1; j <= n; j++) {
// dp[j][0] = dp[j][1];
// dp[j][1] = 0;
// }
}
// for(int i=2; i<=k; i++){
// for(int j=1; j<=n; j++){
// cout << dp[j][i] << endl;
// }
// cout << endl;
// }
int mx = 0;
int last = 0;
for(int i=1; i<=n; i++){
if(k > i)continue;
// cout << dp[i][k] << endl;
if(mx < dp[i][k]){
last = i;
mx = dp[i][k];
}
}
cout << mx << endl;
for(int i=k-1; i>=0; i--){
cout << last << " ";
// cout << last << " " << i << " " << tv[last][i] << endl;
last = tv[last][i];
}
}
