/**
* author: NimaAryan
* created: 2024-08-15 09:11:58
**/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#endif
using i64 = long long;
constexpr i64 inf = 1E15;
struct Line {
i64 a, b;
int i;
i64 operator()(int x) const {
return a * x + b;
}
bool intersects_earlier(const Line& A, const Line& B) {
return (A.b - b) * (a - B.a) <= (B.b - b) * (a - A.a);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<i64> s(n + 1);
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + a[i];
}
vector<i64> f(n + 1);
f[0] = -inf;
vector to(k + 1, vector<int>(n + 1));
iota(to[0].begin(), to[0].end(), 0);
to[0][0] = -1;
for (int kk = 1; kk <= k; ++kk) {
vector<i64> g(n + 1);
vector<Line> f_max(2 * n + 3);
int l = 0, r = 0;
for (int i = 0; i <= n; ++i) {
while (r - l >= 2 && f_max[l](s[i]) < f_max[l + 1](s[i])) {
++l;
}
if (r - l >= 1) {
g[i] = f_max[l](s[i]);
to[kk][i] = f_max[l].i;
} else {
g[i] = -inf;
}
Line fi = Line{s[i], f[i] - s[i] * s[i], i};
while (r - l >= 2 && f_max[r - 2].intersects_earlier(fi, f_max[r - 1])) {
--r;
}
f_max[r++] = fi;
}
f.swap(g);
}
cout << f[n] << "\n";
vector<int> ans;
for (int i = n; k >= 0; i = to[k][i], --k) {
ans.push_back(i);
}
for (int i = ans.size() - 1; i >= 1; --i) {
cout << ans[i] << " ";
}
return 0;
}
