#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// -------------------- GLOBAL DATA --------------------
int n, k;
vector<ll> a, s;
vector<ll> dp_prev, dp_cur;
vector<vector<int>> parent; // parent[t][i] = best split j for dp[t][i]
// compute dp_cur[l..r] using dp_prev and store parent[t][*]
void solve(int t, int l, int r, int optL, int optR) {
if (l > r) return;
int mid = (l + r) >> 1;
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);
}
// -------------------- MAIN --------------------
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[t][i]
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 SPLITS --------------------
vector<int> cuts;
int pos = n;
for (int t = k; t >= 1; t--) {
int j = parent[t][pos];
cuts.push_back(j);
pos = j;
}
reverse(cuts.begin(), cuts.end());
// -------------------- OUTPUT --------------------
cout << answer << "\n";
for (int x : cuts) cout << x << " ";
cout << "\n";
}
