#include <bits/stdc++.h>
using namespace std;
const int mxK = 202, mxN = 1e5+2;
int to[mxK][mxN], dq[mxN], l = 1, r = 1;
long long dpb[mxN], dp[mxN], pref[mxN];
inline long long sq(long long a) {
return a*a;
}
double cord(int x, int y) {
return (double)(dpb[x] - sq(pref[x]) - dpb[y] + sq(pref[y]))/(pref[y] - pref[x]);// (d-b)/(a-c)
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
pref[i] = pref[i-1] + x;
}
for (int i = 1; i <= k; ++i) {
dq[0] = r = l = 0;
for (int j = 1; j <= n; ++j) {
while (r - l > 0 && cord(dq[l], dq[l+1]) <= pref[j]) l++;
dp[j] = dpb[dq[l]] - sq(pref[dq[l]]) + pref[dq[l]] * pref[j];
to[i][j] = dq[l];
while (r - l > 0 && cord(dq[r-1], j) <= cord(dq[r], dq[r-1])) r--;
dq[++r] = j;
}
for (int j = 1; j <= n; ++j) {
dpb[j] = dp[j];
}
}
cout << dp[n] << '\n';
int idx = n;
for (int i = k; i >= 1; --i) {
cout << to[i][idx] << ' ';
idx = to[i][idx];
}
}
