// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 3e18 + 7;
struct LineContainer
{
struct line
{
ll a, b;
mutable ll p;
pair<int, int> par;
bool operator < (const line& o) const {
if(o.a == INF && o.b == INF) return p < o.p;
return a < o.a;
}
};
multiset<line> lc;
ll div(ll a, ll b){
return a / b - ((a ^ b) < 0 && a % b);
}
bool phe(multiset<line>::iterator x, multiset<line>::iterator y){
if(y == lc.end()){
x->p = INF;
return 0;
}
if(x->a == y->a){
if(x->b >= y->b) x->p = INF;
else x->p = -INF;
return x->p >= y->p;
}
x->p = div(x->b - y->b, y->a - x->a);
return x->p >= y->p;
}
void add(ll a, ll b, int i, int j){
auto x = lc.insert({a, b, 0, {i, j}});
auto y = next(x);
while(phe(x, y)) y = lc.erase(y);
if((y = x) != lc.begin() && phe(--x, y))
phe(x, y = lc.erase(y));
while((y = x) != lc.begin() && (--x)->p >= y->p)
phe(x, y = lc.erase(y));
}
pair<ll, pair<int, int>> qr(ll x){
assert(!lc.empty());
line l = *lc.lower_bound({INF, INF, x, {-INF, -INF}});
return {l.a * x + l.b, l.par};
}
};
const int maxn = 1e5 + 10;
int n, k;
ll pref[maxn];
pair<int, int> trace[maxn][210];
// (pref[i] - pref[j]) * pref[j] + dp[j]
// (pref[i] * pref[j]) + (dp[j] - pref[j] * pref[j])
void solve(){
cin >> n >> k;
k++;
for(int i=1; i<=n; ++i){
cin >> pref[i];
pref[i] += pref[i - 1];
}
vector<ll> dp(n + 1, 0);
for(int j=2; j<=k; ++j){
LineContainer lc;
lc.add(pref[j - 1], dp[j - 1] - pref[j - 1] * pref[j - 1], j - 1, j - 1);
vector<ll> nxtdp(n + 1, 0);
for(int i=j; i<=n; ++i){
auto sth = lc.qr(pref[i]);
nxtdp[i] = sth.fi;
trace[i][j] = sth.se;
lc.add(pref[i], dp[i] - pref[i] * pref[i], i, j - 1);
}
dp = nxtdp;
}
cout << dp[n] << '\n';
pair<int, int> sth = {n, k};
for(int i=1; i<k; ++i){
pair<int, int> nxt = trace[sth.fi][sth.se];
cout << nxt.fi << ' ';
sth = nxt;
}
}
signed main(){
// freopen("inp.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
