#include <bits/stdc++.h>
using namespace std;
const int mxK = 202, mxN = 1e5+2;
bool vis[mxN];
int to[mxK][mxN], dq[mxN], l = 0, r = 0;
long long dpb[mxN], dp[mxN], pref[mxN];
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 && pref[j] != pref[j-1] && 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];
if (pref[j] != pref[dq[r-1]]) {
while (r - l > 0 && pref[j] != pref[dq[r-1]] && 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) {
if (!to[i][idx]) {
for (int j = n-1; j >= 1 && i >= 1; --j){
if (!vis[j]) {
--i;
cout << j << ' ';
}
}
break;
}
cout << to[i][idx] << ' ';
idx = to[i][idx];
vis[idx] = 1;
}
}
