#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15;
int tv[N][205];
#define int long long
int a[N];
int n, k;
int dp[N][2];
int pre[N];
// int tv[N][205];
int id = 1;
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][1] = -1e18;
for (int i = min(mid,opr); i >= opl; i--) {
int val = dp[i-1][0] + cost(i, mid);
if (val > dp[mid][1]){
dp[mid][1] = val;
opm = i;
}
}
tv[mid][id] = opm;
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][0] = cost(1, i);
for (int i = 2; i <= k; i++) {
id++;
cal(i, i, n, i-1, n);
for (int j = 1; j <= n; j++) {
dp[j][0] = dp[j][1];
dp[j][1] = 0;
}
}
int mx = -1e18;
int last = 0;
for (int i = 1; i <= n; i++) {
// cout << dp[i][0] << endl;
if (mx < dp[i][0]) {
last = i;
mx = dp[i][0];
}
}
cout << mx << endl;
for (int i = k; i >= 1; i--) {
cout << last << " ";
last = tv[last][i]-1;
}
}
