#include <iostream>
#include <vector>
#include <limits>
#include <numeric>
#include <algorithm>
int main() {
int n, k;
std::cin >> n >> k;
std::vector<int> xs(n);
for (int& x : xs) std::cin >> x;
std::vector<long long> sum(n);
std::partial_sum(xs.begin(), xs.end(), sum.begin());
long long INF = std::numeric_limits<long long>::max();
std::vector<std::vector<long long>> dp(k+1, std::vector<long long>(n, INF));
std::vector<std::vector<int>> back(k+1, std::vector<int>(n, -1));
for (int i = 0; i < n; ++i) {
dp[0][i] = sum[i] * sum[i];
back[0][i] = -1;
}
for (int ik = 1; ik <= k; ++ik) {
for (int i = 0; i < n; ++i) {
long long target = sum[i] / (ik + 1);
int p = std::distance(sum.begin(), std::lower_bound(sum.begin(),
sum.begin() + i,
sum[i] - target));
for (int j = std::max(p+1, ik); j <= i; ++j) {
long long r = sum[i] - sum[j-1];
if (r * (ik+1) > sum[i]) continue;
long long v2 = sum[j-1]*sum[j-1]/ik + r*r;
if (v2 >= dp[ik][i]) break;
long long v = dp[ik-1][j-1] + r*r;
if (dp[ik][i] >= v) {
dp[ik][i] = v;
back[ik][i] = j - 1;
}
else break;
}
for (int j = std::max(p+1, ik); j >= ik; --j) {
long long r = sum[i] - sum[j-1];
if (r * (ik+1) < sum[i]) continue;
long long v2 = sum[j-1]*sum[j-1]/ik + r*r;
if (v2 >= dp[ik][i]) break;
long long v = dp[ik-1][j-1] + r*r;
if (dp[ik][i] >= v) {
dp[ik][i] = v;
back[ik][i] = j - 1;
}
else break;
}
}
}
std::vector<int> ans;
for (int p = n - 1, ik = k; ik; --ik) {
p = back[ik][p];
ans.push_back(p + 1);
}
std::ranges::reverse(ans);
std::cout << ((sum[n-1] * sum[n-1] - dp[k][n-1]) / 2) << "\n";
for (int v : ans) std::cout << v << " ";
std::cout << "\n";
}
