#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e18;
const int MAXN = 1e5 + 5;
const int MAXK = 205;
// Order of operations doesn't matter, the score is always the same.
//
// dp[n][k] = using k operations, how many ways to divide 1...n with maximum score
// dp[n][k] = dp[prv][k-1] + (A[n] - A[prv]) * A[prv]
// dp[n][k] = dp[prv][k-1] + A[n] * A[prv] - A[prv] * A[prv]
// Convex Hull Trick, evaluate x = A[n], y = A[prv] * x + dp[prv][k-1] - A[prv]^2
// A[prv] and A[n] is non decreasing, we can use monotone queue for amortized O(1) insertion and query.
//
// Use flying table on the (int64) DP table, maintaining a separate backtracking table which
// only uses int32 to save memory.
//
// Time Complexity: O(NK)
int N, K;
lint A[MAXN];
lint dp[MAXN][2];
int tr[MAXN][MAXK];
struct Line { // ax + b
int id;
lint a, b;
Line() {}
Line(int id, lint a, lint b) : id(id), a(a), b(b) {}
lint get(lint x) { return a * x + b; }
};
class ConvexHull {
public:
ConvexHull() {}
int sz, ptr = 0;
vector<Line> line;
bool Majorize(Line a, Line b, Line c) { // Check if Intersection(a, c).x <= Intersection(b, c).x
// a1x + b1 = a2x + b2
// x = (b2 - b1) / (a1 - a2)
if (a.a - c.a == 0 && a.a - b.a == 0) return true;
if (a.a - c.a == 0) {
if (c.b - a.b < 0 && a.a - b.a < 0) return false;
if (c.b - a.b > 0 && a.a - b.a > 0) return false;
return true;
}
if (a.a - b.a == 0) {
if (c.b - a.b <= 0 && a.a - b.a <= 0) return true;
if (c.b - a.b >= 0 && a.a - b.a >= 0) return true;
return false;
}
return (1.00 * (c.b - a.b) / (a.a - c.a)) <= (1.00 * (b.b - a.b) / (a.a - b.a));
}
void Insert(Line n) {
sz = line.size();
while (ptr + 1 < sz && Majorize(line[sz - 2], line[sz - 1], n)) {
line.pop_back();
sz--;
}
line.emplace_back(n);
}
pair<int, lint> Query(lint x) {
if (line.empty()) {
return {-1, -INF};
}
sz = line.size();
while (ptr + 1 < sz && line[ptr].get(x) <= line[ptr + 1].get(x)) {
ptr++;
}
return {line[ptr].id, line[ptr].get(x)};
}
void clear() {
ptr = 0;
line.clear();
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
for (int i = 0; i < MAXN; i++) {
for (int j = 0; j < MAXK; j++) {
dp[i][j & 1] = -INF;
tr[i][j] = -1;
}
}
cin >> N >> K;
for (int i = 1; i <= N; i++) {
cin >> A[i];
A[i] += A[i - 1];
}
for (int n = 0; n <= N; n++) {
dp[n][0] = 0;
}
ConvexHull ch;
for (int k = 1; k <= K; k++) {
ch.clear();
for (int n = 1; n <= N; n++) {
auto cost = ch.Query(A[n]);
dp[n][k & 1] = cost.second;
tr[n][k] = cost.first;
ch.Insert(Line(n, A[n], dp[n][(k - 1) & 1] - A[n] * A[n]));
dp[n][(k - 1) & 1] = -INF;
}
}
vector<int> ans;
int n = N, k = K;
while (k > 0) {
ans.emplace_back(tr[n][k]);
n = tr[n][k--];
}
reverse(begin(ans), end(ans));
cout << dp[N][K & 1] << "\n";
for (auto i : ans) {
cout << i << " ";
}
cout << "\n";
return 0;
}
