#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
using ll = long long;
struct Line {
mutable ll k, m, p, id;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
const ll inf = LLONG_MAX;
ll div(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b); }
bool isect(iterator x, iterator y) {
if (y == end()) { x->p = inf; return false; }
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ll k, ll m, ll id) {
auto z = insert({k, m, 0, id}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
pair<ll, int> query(ll x) {
assert(!empty());
auto l = *lower_bound(x);
return make_pair(l.k * x + l.m, l.id);
}
};
const int MAXN = 1e5+1;
const int MAXK = 201;
ll dp[MAXK][MAXN];
ll arr[MAXN];
ll transition[MAXK][MAXN];
int nb_elem;
int main(void)
{
int nb_split;
cin >> nb_elem >> nb_split;
for (int i(0); i < nb_elem; ++i)
cin >> arr[i];
vector<ll> suffix_sum(nb_elem+1);
suffix_sum[nb_elem] = 0;
for (int i(nb_elem-1); i >= 0; --i)
suffix_sum[i] = suffix_sum[i+1] + arr[i];
for (int splits(1); splits <= nb_split; ++splits)
dp[splits][nb_elem-1] = -2e18;
LineContainer lichao;
for (int splits(1); splits <= nb_split; ++splits)
{
lichao.clear();
for (int id(nb_elem -2); id >= 0; --id)
{
if (dp[splits-1][id+1] >= 0)
lichao.add(suffix_sum[id+1], dp[splits-1][id+1] - suffix_sum[id+1] * suffix_sum[id+1], id);
if (id == nb_elem - 1)
continue;
if (!lichao.empty())
{
auto [val, nxt] = lichao.query(suffix_sum[id]);
dp[splits][id] = val;
transition[splits][id] = nxt;
}
else
dp[splits][id] = -2e18;
}
}
cout << dp[nb_split][0] << endl;
int cur(0);
for (int i(0); i < nb_split; ++i)
{
assert(dp[nb_split-i][cur] >= 0);
cur = transition[nb_split-i][cur] + 1;
cout << cur << ' ';
}
cout << endl;
}
