#include <iostream>
#include <algorithm>
using namespace std;
const long long inf = 1LL << 60;
int n, m, c, s[100009], d[100009], p[209][100009]; long long dp[100009], ndp[100009];
bool comp(long long xa, long long xb, long long ya, long long yb) {
// judge if xa * xb >= ya * yb
int xa1 = xa >> 30, xa0 = xa & ((1 << 30) - 1);
int xb1 = xb >> 30, xb0 = xb & ((1 << 30) - 1);
int ya1 = ya >> 30, ya0 = ya & ((1 << 30) - 1);
int yb1 = yb >> 30, yb0 = yb & ((1 << 30) - 1);
long long xc3 = 0;
long long xc2 = 1LL * xa1 * xb1;
long long xc1 = 1LL * xa1 * xb0 + 1LL * xa0 * xb1;
long long xc0 = 1LL * xa0 * xb0;
long long yc3 = 0;
long long yc2 = 1LL * ya1 * yb1;
long long yc1 = 1LL * ya1 * yb0 + 1LL * ya0 * yb1;
long long yc0 = 1LL * ya0 * yb0;
xc1 += xc0 >> 30; xc0 &= ((1 << 30) - 1);
xc2 += xc1 >> 30; xc1 &= ((1 << 30) - 1);
xc3 += xc2 >> 30; xc2 &= ((1 << 30) - 1);
yc1 += yc0 >> 30; yc0 &= ((1 << 30) - 1);
yc2 += yc1 >> 30; yc1 &= ((1 << 30) - 1);
yc3 += yc2 >> 30; yc2 &= ((1 << 30) - 1);
if (xc3 != yc3) return xc3 > yc3;
if (xc2 != yc2) return xc2 > yc2;
if (xc1 != yc1) return xc1 > yc1;
return xc0 >= yc0;
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> s[i + 1];
s[i + 1] += s[i];
}
fill(dp + 1, dp + n + 1, inf);
for (int i = 0; i <= m; ++i) {
for (int j = 0; j <= n; ++j) {
while (c >= 2 && (s[j] - s[d[c - 1]]) * (dp[d[c - 1]] - dp[d[c - 2]]) >= (s[d[c - 1]] - s[d[c - 2]]) * (dp[j] - dp[d[c - 1]])) {
c--;
}
d[c++] = j;
}
int ptr = 0;
for (int j = 0; j <= n; ++j) {
while (ptr + 1 != c && dp[d[ptr]] - 2 * s[j] * s[d[ptr]] > dp[d[ptr + 1]] - 2 * s[j] * s[d[ptr + 1]]) ptr++;
ndp[j] = dp[d[ptr]] + 2LL * (s[j] - s[d[ptr]]) * s[j];
p[i][j] = d[ptr];
}
copy(ndp, ndp + n + 1, dp);
}
cout << s[n] * s[n] - dp[n] / 2 << '\n';
int pos = n;
for (int i = m; i >= 1; --i) {
pos = p[i][pos];
cout << pos << (i != 1 ? ' ' : '\n');
}
return 0;
}
