#include <bits/stdc++.h>
using namespace std;
class cht_t {
public:
class line_t {
public:
int64_t a, b;
line_t(int64_t a, int64_t b) : a(a), b(b) {}
int64_t operator()(const int64_t& x) const { return a * x + b; }
int64_t intersect(const line_t& other) const {
int64_t x = (b - other.b) / (other.a - a);
while ((*this)(x) <= other(x)) x--;
while ((*this)(x) > other(x)) x++;
return x;
}
};
deque<pair<line_t, int>> dq;
void insert(int64_t a, int64_t b, int id) {
line_t newline(a, b);
while (dq.size() > 1 && dq.back().first.intersect(dq[dq.size() - 2].first) >= newline.intersect(dq.back().first)) dq.pop_back();
dq.emplace_back(newline, id);
}
pair<int64_t, int> getmin(const int64_t& x) {
while (dq.size() > 1 && dq[0].first(x) >= dq[1].first(x)) dq.pop_front();
return {dq[0].first(x), dq[0].second};
}
};
int main() {
int n, k;
cin >> n >> k;
k++;
vector<int> a;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x) a.emplace_back(x);
}
n = a.size();
k = min(k, n);
int64_t res = 1ll * accumulate(a.begin(), a.end(), 0ll) * accumulate(a.begin(), a.end(), 0ll);
for (int i = 0; i < n; i++) res -= 1ll * a[i] * a[i];
// f[i][j] = min(f[k][j - 1] + (ps[i] - ps[k]) * (ps[i] - ps[k]))
// f[i][j] = min(f[k][j - 1] + ps[k] * ps[k] + pss[k] - 2 * ps[k] * ps[i]) + ps[i] * ps[i] - pss[i];
// -----------------v----------------- ----v---- ---v---
// b a x
vector<vector<int64_t>> f(n, vector<int64_t>(k));
vector<vector<int>> trace(n, vector<int>(k));
vector<cht_t> cht(k);
int64_t ps = 0, pss = 0;
for (int i = 0; i < n; i++) {
ps += a[i], pss += 1ll * a[i] * a[i];
for (int j = k - 1; j >= 0; j--) {
if (j > i) continue;
if (j) {
auto p = cht[j - 1].getmin(ps);
f[i][j] = p.first + ps * ps - pss;
trace[i][j] = p.second;
} else {
f[i][j] = ps * ps - pss;
trace[i][j] = -1;
}
cht[j].insert(-2 * ps, f[i][j] + ps * ps + pss, i);
}
}
vector<int> ans;
int ii = n - 1, jj = k - 1;
while (ii != -1) ans.emplace_back(trace[ii][jj] + 1), ii = trace[ii][jj], jj--;
ans.pop_back();
reverse(ans.begin(), ans.end());
cout << (res - f[n - 1][k - 1]) / 2 << '\n';
for (int x : ans) cout << x << ' ';
}
