/**
* 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;
using i128 = __int128_t;
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);
deque<Line> f_max;
for (int i = 0, z = 0; i <= n; ++i) {
while (z >= 2 && f_max[0](s[i]) < f_max[1](s[i])) {
f_max.pop_front();
--z;
}
if (z >= 1) {
g[i] = f_max[0](s[i]);
to[kk][i] = f_max[0].i;
} else {
g[i] = -inf;
}
Line fi = Line{s[i], f[i] - s[i] * s[i], i};
while (z >= 2 && f_max[z - 2].intersects_earlier(fi, f_max[z - 1])) {
f_max.pop_back();
--z;
}
f_max.push_back(fi);
++z;
}
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;
}
