#include <bits/stdc++.h>
using namespace std;
const int N = 100005, K = 205;
const long long inf = 1e18;
int n, k;
long long a[N];
long long f[N][2];
int trace[N][K];
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> k; ++k;
for (int i = 1; i <= n; ++i) cin >> a[i], a[i] += a[i-1];
for (int i = 0; i <= n; ++i) f[i][0] = inf;
f[0][0] = 0;
for (int j = 1; j <= k; ++j) {
for (int i = 0; i <= n; ++i) f[i][j & 1] = inf;
int pt = 0;
for (int i = 1; i <= n; ++i) {
while(pt < i - 1) {
long long cur = f[pt][1 - (j&1)] + (a[i] - a[pt]) * (a[i] - a[pt]);
long long nxt = f[pt + 1][1 - (j&1)] + (a[i] - a[pt + 1]) * (a[i] - a[pt + 1]);
if (cur > nxt) ++pt; else break;
}
f[i][j & 1] = min(f[i][j & 1], f[pt][1 - (j&1)] + (a[i] - a[pt]) * (a[i] - a[pt]));
trace[i][j] = pt;
}
}
long long ans = f[n][k & 1];
ans = (a[n] * a[n] - ans) / 2;
printf("%lld\n", ans);
vector<int> vec;
while(n) {
n = trace[n][k--];
vec.push_back(n);
}
vec.pop_back();
for (int i = vec.size()-1; i >= 0; --i) printf("%d ", vec[i]); printf("\n");
}
