#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
const int MAXN = 1e5 + 5;
const ll NEG_INF = LLONG_MIN / 2;
ll p[MAXN], xs[MAXN];
int SZ, cip[MAXN]; // cip[i] = compressed index of p[i]
struct Line {
ll m = 0, b = NEG_INF; int idx = -1;
ll eval(int c) const { return m * xs[c] + b; }
};
// Static Li Chao tree: node 2*nd = left child, 2*nd+1 = right
Line t[4 * MAXN];
void reset() {
fill(t + 1, t + 4 * SZ + 2, Line{0, NEG_INF, -1});
}
void upd(Line li, int nd, int l, int r) {
int m = (l + r) / 2;
if (li.eval(m) > t[nd].eval(m)) swap(li, t[nd]);
if (l == r) return;
if (li.eval(l) > t[nd].eval(l)) upd(li, 2*nd, l, m);
else if (li.eval(r) > t[nd].eval(r)) upd(li, 2*nd+1, m+1, r);
}
pli qry(int c, int nd, int l, int r) {
pli res = {t[nd].eval(c), t[nd].idx};
if (l == r) return res;
int m = (l + r) / 2;
if (c <= m) return max(res, qry(c, 2*nd, l, m));
else return max(res, qry(c, 2*nd+1, m+1, r));
}
ll dp[MAXN][2];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, k; cin >> n >> k;
for (int i = 1; i <= n; i++) { int x; cin >> x; p[i] = p[i-1] + x; }
// Build compressed x-axis once
copy(p, p + n + 1, xs);
sort(xs, xs + n + 1);
SZ = unique(xs, xs + n + 1) - xs;
for (int i = 0; i <= n; i++)
cip[i] = (int)(lower_bound(xs, xs + SZ, p[i]) - xs);
// pr[i][j]: backtrack pointer — allocate as flat array for speed
vector<int> pr((n + 1) * (k + 1), 0);
auto PR = [&](int i, int j) -> int& { return pr[i * (k + 1) + j]; };
for (int j = 1; j <= k; j++) {
reset();
for (int i = j + 1; i <= n; i++) {
upd({p[i-1], dp[i-1][0] - p[i-1]*p[i-1], i-1}, 1, 0, SZ-1);
auto q = qry(cip[i], 1, 0, SZ - 1);
dp[i][1] = q.first;
PR(i, j) = q.second;
dp[i-1][0] = dp[i-1][1];
}
dp[n][0] = dp[n][1];
}
cout << dp[n][0] << '\n';
int cur = n;
for (int j = k; j >= 1; j--) { cout << PR(cur, j) << ' '; cur = PR(cur, j); }
}
