#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MXN = 100005;
const int MXK = 205;
const ll INF = 3e18; // Large enough for comparisons
struct Line {
ll m, b;
int id;
// Evaluation using the original prefix sum value
inline ll eval(ll x) const { return m * x + b; }
};
// Global arrays for maximum performance and cache locality
ll p[MXN], coords[MXN];
ll dp[2][MXN];
int pr[MXK][MXN];
Line tree[4 * MXN];
bool has[4 * MXN];
int num_coords;
// Faster, non-dynamic update (standard Segment Tree indexing)
void upd(int v, int l, int r, Line newL) {
while (true) {
if (!has[v]) {
tree[v] = newL;
has[v] = true;
return;
}
int mid = l + (r - l) / 2;
ll cur_val = tree[v].eval(coords[mid]);
ll new_val = newL.eval(coords[mid]);
if (new_val > cur_val) swap(newL, tree[v]);
if (l == r) return;
// Branching logic to find where the other line might be better
if (newL.eval(coords[l]) > tree[v].eval(coords[l])) {
v = 2 * v;
r = mid;
} else if (newL.eval(coords[r]) > tree[v].eval(coords[r])) {
v = 2 * v + 1;
l = mid + 1;
} else {
return;
}
}
}
// Iterative query (path down the tree)
inline pair<ll, int> qry(int x_rank) {
ll best_v = -INF;
int best_id = -1;
ll target_x = coords[x_rank];
int v = 1, l = 1, r = num_coords;
while (true) {
if (has[v]) {
ll current_val = tree[v].eval(target_x);
if (current_val > best_v) {
best_v = current_val;
best_id = tree[v].id;
}
}
if (l == r) break;
int mid = l + (r - l) / 2;
if (x_rank <= mid) {
v = 2 * v;
r = mid;
} else {
v = 2 * v + 1;
l = mid + 1;
}
}
return {best_v, best_id};
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, k;
if (!(cin >> n >> k)) return 0;
for (int i = 1; i <= n; i++) {
ll x; cin >> x;
p[i] = p[i - 1] + x;
coords[i] = p[i];
}
// 1. Coordinate Compression on p[i]
sort(coords + 1, coords + n + 1);
num_coords = unique(coords + 1, coords + n + 1) - (coords + 1);
auto get_rank = [&](ll val) {
return lower_bound(coords + 1, coords + num_coords + 1, val) - coords;
};
// 2. DP with Rolling Array
for (int j = 1; j <= k; j++) {
int cur = j % 2, prev = (j - 1) % 2;
// Fast reset of the tree presence array
memset(has, 0, sizeof(bool) * (4 * num_coords + 1));
for (int i = 1; i <= n; i++) {
// Query for the best previous split p < i
if (i > j) {
pair<ll, int> res = qry(get_rank(p[i]));
dp[cur][i] = res.first;
pr[j][i] = res.second;
} else {
dp[cur][i] = -1e18; // Impossible state
}
// Add the line from the previous layer
// Split index i must be < n to ensure parts are non-empty
if (i >= j && i < n && (j == 1 || dp[prev][i] > -1e17)) {
ll intercept = dp[prev][i] - p[i] * p[i];
upd(1, 1, num_coords, {p[i], intercept, i});
}
}
}
// Output result and path
cout << dp[k % 2][n] << "\n";
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;
}
