#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG = -(1LL << 60);
int n, k;
vector<ll> pref;
vector<ll> dpPrev, dpCur;
vector<vector<int>> parentPos;
ll value(int j, int i) {
if (dpPrev[j] == NEG) return NEG;
ll leftPart = pref[i] - pref[j];
ll rightPart = pref[n] - pref[i];
return dpPrev[j] + leftPart * rightPart;
}
void computeLayer(int l, int r, int optL, int optR, int layer) {
if (l > r) return;
int mid = (l + r) / 2;
ll bestValue = NEG;
int bestPos = -1;
int upper = min(optR, mid - 1);
for (int j = optL; j <= upper; j++) {
ll curValue = value(j, mid);
// Use >= to choose the rightmost optimum.
// This keeps monotonicity clean even with zero values.
if (curValue >= bestValue) {
bestValue = curValue;
bestPos = j;
}
}
dpCur[mid] = bestValue;
parentPos[layer][mid] = bestPos;
computeLayer(l, mid - 1, optL, bestPos, layer);
computeLayer(mid + 1, r, bestPos, optR, layer);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
pref.assign(n + 1, 0);
for (int i = 1; i <= n; i++) {
ll x;
cin >> x;
pref[i] = pref[i - 1] + x;
}
dpPrev.assign(n, NEG);
dpCur.assign(n, NEG);
parentPos.assign(k + 1, vector<int>(n, -1));
dpPrev[0] = 0;
for (int layer = 1; layer <= k; layer++) {
fill(dpCur.begin(), dpCur.end(), NEG);
/*
We compute dp[layer][i] for valid last split positions i.
Need:
- i >= layer, because layer splits need at least layer positions.
- i <= n - 1, because split after n is invalid.
- previous split j is in [layer - 1, i - 1].
*/
computeLayer(layer, n - 1, layer - 1, n - 2, layer);
dpPrev.swap(dpCur);
}
ll answer = NEG;
int lastSplit = -1;
for (int i = k; i <= n - 1; i++) {
if (dpPrev[i] > answer) {
answer = dpPrev[i];
lastSplit = i;
}
}
vector<int> splits(k + 1);
int cur = lastSplit;
for (int layer = k; layer >= 1; layer--) {
splits[layer] = cur;
cur = parentPos[layer][cur];
}
cout << answer << '\n';
for (int i = 1; i <= k; i++) {
cout << splits[i];
if (i < k) cout << ' ';
}
cout << '\n';
return 0;
}
