#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, k;
vector<ll> a, s;
vector<ll> dp_prev, dp_cur;
vector<vector<int>> parent; // parent[t][i] = best j for dp[t][i]
// Compute dp_cur[l..r] using dp_prev
void solve(int t, int l, int r, int optL, int optR) {
if (l > r) return;
int mid = (l + r) / 2;
pair<ll,int> best = {LLONG_MIN, -1};
for (int j = optL; j <= min(mid-1, optR); j++) {
ll val = dp_prev[j] + s[j] * (s[mid]-s[j]);
if (val > best.first) {
best = {val, j};
}
}
dp_cur[mid] = best.first;
parent[t][mid] = best.second;
int opt = best.second;
solve(t, l, mid-1, optL, opt);
solve(t, mid+1, r, opt, optR);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
a.assign(n+1, 0);
s.assign(n+1, 0);
for (int i=1; i<=n; i++) cin >> a[i];
for (int i=1; i<=n; i++) s[i] = s[i-1]+a[i];
dp_prev.assign(n+1, 0);
dp_cur.assign(n+1, 0);
parent.assign(k+1, vector<int>(n+1, -1));
for (int t=1; t<=k; t++) {
solve(t, 1, n, 0, n-1);
dp_prev = dp_cur;
}
ll answer = dp_prev[n];
// --------------- RECONSTRUCT CUT POSITIONS ---------------
vector<int> cuts;
int pos = n;
for (int t = k; t >= 1; t--) {
int j = parent[t][pos];
cuts.push_back(j); // split after position j
pos = j;
}
reverse(cuts.begin(), cuts.end());
// ---------------- OUTPUT ----------------
cout << answer << "\n";
for (int i = 0; i < (int)cuts.size(); i++) {
if (i > 0) cout << " ";
cout << cuts[i];
}
cout << "\n";
}
