#include <iostream>
#include <vector>
using namespace std;
constexpr int N = 1e5 + 5;
constexpr int K = 200 + 5;
constexpr long long INF = 1e18;
int s[N];
long long f[N];
int trace[K][N];
struct Ray {
int trace;
int slope;
long long offset;
long long stop;
long long operator&(const Ray &other) const {
int dm = slope - other.slope;
return dm == 0 ? -INF : (other.offset - offset) / dm;
}
long long operator()(const int x) const {
return 1ll * slope * x + offset;
}
};
vector<Ray> hull;
void insert(Ray l) {
if (hull.empty()) {
hull.push_back(l);
return;
}
while (hull.size() >= 2 && (l & hull.back()) <= hull[hull.size() - 2].stop) {
hull.pop_back();
}
hull.back().stop = l & hull.back();
hull.push_back(l);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// freopen("input.txt", "r", stdin);
int n, k;
cin >> n >> k;
k++;
s[0] = 0;
for (int i = 1; i <= n; i++) {
cin >> s[i];
s[i] += s[i - 1];
}
for (int i = 0; i <= n; i++) {
f[i] = 0;
}
for (int l = 2; l <= k; l++) {
hull.clear();
long long flast = f[0];
int it = 0;
for (int i = 1; i <= n; i++) {
insert(Ray{i - 1, s[i - 1], flast - 1ll * s[i - 1] * s[i - 1], INF});
flast = f[i];
it = min(it, (int) hull.size() - 1);
while (hull[it].stop < s[i]) it++;
f[i] = hull[it](s[i]);
trace[l][i] = hull[it].trace;
}
}
cout << f[n] << '\n';
for (int i = trace[k][n], l = k - 1; l; i = trace[l--][i]) {
f[l] = i;
}
for (int i = 1; i < k; i++) {
cout << f[i] << ' ';
}
return 0;
}
