#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5+5, K = 205;
ll n, k;
ll a[N], pref[N];
ll dp[N][2];
int opt[N][K];
ll cost(int i, int j) {
return (pref[j] - pref[i-1]) * (pref[n] - pref[j]);
}
void solve(int j, int l, int r, int optL, int optR) {
if(l > r) return;
int i = (l+r)/2;
for(int k = optL; k <= min(i-1, optR); k++) {
ll cur = dp[k][(j-1)&1] + cost(k, i-1);
if(dp[i][j&1] <= cur)
dp[i][j&1] = cur, opt[i][j] = k;
}
solve(j, l, i-1, optL, opt[i][j]);
solve(j, i+1, r, opt[i][j], optR);
}
void solve() {
cin >> n >> k;
for(int i = 1; i <= n; i++)
cin >> a[i];
pref[0] = 0;
for(int i = 1; i <= n; i++) {
dp[i][0] = 0;
opt[i][0] = 0;
pref[i] = pref[i-1] + a[i];
}
for(int j = 1; j <= k; j++) {
for(int i = 1; i <= n; i++)
dp[i][j&1] = -1;
solve(j, 1, n, j, n-1);
}
ll ans = -1; int cur = -1;
for(int i = 1; i <= n; i++) {
if(ans < dp[i][k&1])
ans = dp[i][k&1], cur = i;
}
cout << ans << '\n';
for(int i = k; i > 0; i--) {
cout << cur-1 << ' ';
cur = opt[cur][i];
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
solve();
return 0;
}
