#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
long long dp[2][100008];
int par[208][100008];
long long pf[100008], pf_sq[100008];
long long x, y;
long long f(int l, int r) {
x = pf[r] - pf[l - 1]; y = pf_sq[r] - pf_sq[l - 1];
return (x * x - y) / 2;
}
void DP(int level, int l, int r, int optl, int optr) {
if (l > r) return;
int mid = (l + r) / 2, start = min(mid - 1, optr), optm = 0;
int cur = (level & 1);
dp[cur][mid] = inf;
for (int i = start; i >= optl; --i) {
if (dp[cur][mid] > dp[cur ^ 1][i] + f(i + 1, mid)) {
dp[cur][mid] = dp[cur ^ 1][i] + f(i + 1, mid);
par[level][mid] = optm = i;
}
}
// cout << level << ' ' << mid << ' ' << optl << ' ' << optr << ' ' << optm << ' ' << dp[cur][mid] << "!!\n";
DP(level, l, mid - 1, optl, optm); DP(level, mid + 1, r, optm, optr);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, k; cin >> n >> k; ++k;
for (int i = 1; i <= n; ++i) {
cin >> x;
pf[i] = pf[i - 1] + x;
pf_sq[i] = pf_sq[i - 1] + x * x;
}
for (int i = 1; i <= n; ++i) dp[0][i] = inf;
for (int i = 1; i <= k; ++i) {
dp[i & 1][0] = inf; fill(dp[i & 1] + 1, dp[i & 1] + n + 1, 0);
DP(i, 1, n, 0, n - 1);
}
cout << f(1, n) - dp[k & 1][n] << '\n'; int pt = n;
vector<int> cuts;
for (int i = k; i > 1; --i) cuts.push_back(par[i][pt]), pt = par[i][pt];
reverse(cuts.begin(), cuts.end());
for (int i : cuts) cout << i << ' ';
}
