#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn = 100005;
const int mxk = 205;
const ll INF = 2e18;
struct line {
ll m = 0, b = -INF;
int idx = -1;
// We only evaluate if the line has been properly initialized
ll eval(ll x) const {
if (idx == -1) return -INF;
return m * x + b;
}
};
struct node {
int lc, rc;
line li;
} tn[mxn * 40]; // Coordinate compression makes this size safe
int cnt = 0;
ll coords[mxn];
int num_coords = 0;
int create() {
cnt++;
tn[cnt].lc = tn[cnt].rc = -1;
tn[cnt].li = line();
return cnt;
}
void upd(line li, int i, int l, int r) {
int m = l + (r - l) / 2;
bool mid_better = li.eval(coords[m]) > tn[i].li.eval(coords[m]);
if (mid_better) swap(li, tn[i].li);
if (l == r) return;
if (li.eval(coords[l]) > tn[i].li.eval(coords[l])) {
if (tn[i].lc == -1) tn[i].lc = create();
upd(li, tn[i].lc, l, m);
} else if (li.eval(coords[r]) > tn[i].li.eval(coords[r])) {
if (tn[i].rc == -1) tn[i].rc = create();
upd(li, tn[i].rc, m + 1, r);
}
}
pair<ll, int> qry(int x_rank, int i, int l, int r) {
if (i == -1 || tn[i].li.idx == -1) return {-INF, -1};
ll x_val = coords[x_rank];
pair<ll, int> res = {tn[i].li.eval(x_val), tn[i].li.idx};
if (l == r) return res;
int m = l + (r - l) / 2;
if (x_rank <= m) res = max(res, qry(x_rank, tn[i].lc, l, m));
else res = max(res, qry(x_rank, tn[i].rc, m + 1, r));
return res;
}
ll p[mxn];
ll dp[2][mxn];
int pr[mxk][mxn];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, k;
if (!(cin >> n >> k)) return 0;
vector<ll> temp_p;
for (int i = 1; i <= n; i++) {
ll x; cin >> x;
p[i] = p[i - 1] + x;
temp_p.push_back(p[i]);
}
// Coordinate Compression
sort(temp_p.begin(), temp_p.end());
temp_p.erase(unique(temp_p.begin(), temp_p.end()), temp_p.end());
num_coords = temp_p.size();
for (int i = 0; i < num_coords; i++) coords[i + 1] = temp_p[i];
auto get_rank = [&](ll val) {
return lower_bound(coords + 1, coords + num_coords + 1, val) - coords;
};
// dp[0][i] is the score for 0 splits (always 0)
for (int i = 0; i <= n; i++) dp[0][i] = 0;
for (int j = 1; j <= k; j++) {
cnt = 0;
int root = create();
int cur = j % 2;
int prev = (j - 1) % 2;
for (int i = 1; i <= n; i++) {
// 1. Query first: Find best split point p < i
if (i > j) {
auto q = qry(get_rank(p[i]), root, 1, num_coords);
dp[cur][i] = q.first;
pr[j][i] = q.second;
} else {
dp[cur][i] = -1; // Mark as impossible/unreachable
}
// 2. Add split candidate AFTER index i for the NEXT piece
// To ensure parts are non-empty, i must be >= j and i < n
if (i >= j && i < n && dp[prev][i] != -1) {
ll intercept = dp[prev][i] - p[i] * p[i];
upd({p[i], intercept, i}, root, 1, num_coords);
}
}
}
cout << dp[k % 2][n] << "\n";
// Backtracking from split s_k down to s_1
int curr_n = n;
for (int j = k; j >= 1; j--) {
curr_n = pr[j][curr_n];
cout << curr_n << (j == 1 ? "" : " ");
}
cout << endl;
return 0;
}
