#include <bits/stdc++.h>
using namespace std;
#define int long long
struct L {
int a, b, from;
int operator()(int x) { return a * x + b; }
pair<int, int> inter(L &he) const
{
int up = he.b - b;
int down = a - he.a;
return {up, down};
}
};
struct CHT {
vector<L> hull;
int start = 0;
pair<int, int> query(int x, int i)
{
while(start <= (int)hull.size() - 2) {
L A = hull[start], B = hull[start + 1];
if(B.from < i && A(x) <= B(x))
start++;
else
break;
}
return {hull[start](x), hull[start].from};
}
void add(L x)
{
if(!hull.empty() && hull.back().a == x.a) {
if(hull.back().b < x.b) {
hull.pop_back();
}
else {
return;
}
}
while(start <= (int)hull.size() - 2) {
L A = hull.end()[-2], B = hull.end()[-1];
auto one = A.inter(B), two = B.inter(x);
assert(one.second && two.second);
if(one.first * two.second > two.first * one.second) {
hull.pop_back();
}
else {
break;
}
}
hull.push_back(x);
}
};
int sq(int x) { return x * x; }
int32_t main()
{
cin.tie(0)->sync_with_stdio(0);
int n, k;
cin >> n >> k;
vector<int> p(n + 1);
for(int i = 1; i <= n; i++) {
cin >> p[i];
p[i] += p[i - 1];
}
CHT dp;
for(int i = 1; i <= n; i++) {
dp.add({p[i], -sq(p[i]), i});
}
vector<vector<int32_t>> come(k + 1, vector<int32_t>(n + 1));
for(int now = 1; now <= k; now++) {
CHT new_dp;
for(int i = now + 1; i <= n; i++) {
auto in = dp.query(p[i], i);
if(now == k && i == n) {
cout << in.first << '\n';
}
come[now][i] = in.second;
if(i < n) {
new_dp.add({p[i], in.first - sq(p[i]), i});
}
}
dp = new_dp;
}
vector<int> print(k);
int nn = n, kk = k;
while(kk) {
nn = come[kk][nn];
kk--;
print[kk] = nn;
}
for(int i = 0; i < k; i++) {
cout << print[i] << " ";
}
cout << '\n';
}
