#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll N = 1e5 + 5;
const ll base = 37;
const ll inf = LLONG_MAX/4;
const ll mod = 1e9 + 7;
#define bit(x,y) ((x >> y) & 1)
struct ConvexHullTrick {
const ll Inf = 1e18;
ll n;
ll a[N], b[N], id[N];
vector<ll> line;
vector<ld> poll;
ConvexHullTrick() {
poll.emplace_back(-Inf);
}
void clea()
{
line.clear();
poll.clear();
poll.emplace_back(-Inf);
}
ld ff(ll x, ll y) {
return (ld) 1.0 * (b[x] - b[y]) / (a[y] - a[x]);
}
void Add(ll i) {
while (!line.empty()) {
if (a[line.back()] == a[i]) {
if (b[line.back()] < b[i]) {
break;
} else {
line.pop_back();
if (!line.empty()) {
poll.pop_back();
}
}
} else {
if (line.size() < 2) {
break;
}
if (ff(i, line[line.size() - 2]) < ff(i, line.back())) {
break;
} else {
line.pop_back();
if (!line.empty()) {
poll.pop_back();
}
}
}
}
if (line.empty() || a[line.back()] != a[i]) {
if (!line.empty()) {
poll.emplace_back(ff(i, line.back()));
}
line.emplace_back(i);
}
}
pair<ll,ll> get(ll x) {
ll j = upper_bound(poll.begin(), poll.end(), (ld) x) - poll.begin() - 1;
return {a[line[j]] * x + b[line[j]],id[line[j]]};
}
};
ll a[N],s[N];
ll d[2][N];
int v[205][N];
ConvexHullTrick f;
int main()
{
ll n,k;
cin >> n >> k;
ll i,j;
for(i = 1;i <= n;i++) cin >> a[i];
for(i = 1;i <= n;i++) s[i] = s[i - 1] + a[i];
f.n = n + 5;
ll e = 0;
for(i = 2;i <= k + 1;i++)
{
f.clea();
for(j = i;j <= n;j++)
{
f.a[j - i + 1] = s[j - 1];
f.b[j - i + 1] = d[e][j - 1] - (s[j - 1] * s[j - 1]);
f.id[j - i + 1] = j - 1;
f.Add(j - i + 1);
pair<ll,ll> tmp = f.get(s[j]);
d[1 - e][j] = tmp.first;
v[i][j] = tmp.second;
}
e = 1 - e;
}
cout << d[e][n] << "\n";
i = k + 1;
j = n;
while(i > 1)
{
cout << v[i][j] << " ";
j = v[i][j];
i--;
}
}
