#include <bits/stdc++.h>
using namespace std;
#define llint long long
void openFile() {
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
#ifdef Tr___
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
#endif
}
const int maxN = 1e5 + 5;
const int maxM = 2e2 + 5;
const llint INF = 1e9 + 7;
int N, K;
llint a[maxN];
llint f[maxN][2];
struct line {
llint a, b;
int id;
line() {}
line(llint a, llint b, int id): a(a), b(b), id(id) {}
} l[maxN];
int nLines = 0;
int last = 0;
void enter() {
cin >> N >> K;
for (int i = 1; i <= N; ++i) {
cin >> a[i];
a[i] += a[i - 1];
}
}
void clear() {
for (int i = 1; i <= nLines; ++i) {
l[i].id = 0;
}
nLines = 0;
last = 1;
}
void update(int id, llint a, llint b) {
while (nLines >= 2 && last < nLines) {
line lef = l[nLines - 1];
line rig = l[nLines];
if ((b - lef.b) * (lef.a - rig.a) <= (lef.a - a) * (rig.b - lef.b)) {
--nLines;
}
else {
break;
}
}
last = min(last, nLines);
l[++nLines] = line(a, b, id);
}
inline llint get(int id, llint x) {
return l[id].a * x + l[id].b;
}
inline int query(llint x) {
//so important!!!
if (last > nLines)
last = nLines;
last = max(last, 1);
if (nLines == 0) return 0;
while (last < nLines && get(last, x) <= get(last + 1, x)) ++last;
return last;
}
int t[maxN][maxM];
void solve() {
for (int k = 1; k <= K; ++k) {
clear();
for (int i = k; i <= N; ++i) {
int la = query(a[i]);
f[i][k&1] = get(la, a[i]);
t[i][k] = l[la].id;
update(i, a[i], f[i][!(k&1)] - a[i] * a[i]);
}
}
printf("%lld\n", f[N][K&1]);
int trace = t[N][K];
vector<int> res;
res.clear();
while (trace) {
res.push_back(trace);
trace = t[trace][--K];
}
reverse(res.begin(), res.end());
for (int x : res) {
printf("%d ", x);
}
}
int main() {
openFile();
enter();
solve();
return 0;
}
