#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define inf 1e12
typedef long long ll;
typedef pair<ll, ll> pii;
const ll N = 1e5 + 10, K = 205;
int n, k, a[N], par[N][K];
ll p[N];
vector<pair<ll, pii>> hull[K];
inline bool cmp(pii x, pii y){
if ((x.F / x.S) != (y.F / y.S))
return (x.F / x.S) > (y.F / y.S);
x.F %= x.S;
y.F %= y.S;
return (x.F * y.S) > (y.F * x.S);
}
inline bool useful(pii x, pii y, pii z){
return cmp({x.S - y.S, y.F - x.F}, {y.S - z.S, z.F - y.F});
}
inline void insert(int id, int ind, pii L){
while (hull[id].size() and hull[id].back().S.F == L.F){
if (hull[id].back().S.S < L.S)
hull[id].pop_back();
else
return ;
}
while (hull[id].size() > 1 and !useful(hull[id][hull[id].size() - 2].S, hull[id].back().S, L))
hull[id].pop_back();
hull[id].push_back({ind, L});
}
inline ll f(pii L, ll x){
return x * L.F + L.S;
}
inline pair<ll, int> query(int id, int ind, ll x){
if (hull[id][0].F <= ind) return {-inf, -1};
pair<ll, int> ans = {f(hull[id][0].S, x), hull[id][0].F};
int lo = 0, hi = hull[id].size();
while (hi - lo > 1){
int mid = (lo + hi) / 2;
if (hull[id][mid].F <= ind){
hi = mid;
continue;
}
ll ans1 = f(hull[id][mid - 1].S, x);
ll ans2 = f(hull[id][mid].S, x);
if (ans1 < ans2){
ans = {ans2, hull[id][mid].F};
lo = mid;
}
else{
ans = {ans1, hull[id][mid - 1].F};
hi = mid;
}
}
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for (ll i = 1; i <= n; i ++)
cin >> a[i], p[i] = p[i - 1] + a[i];
for (ll i = n; i > 0; i--)
insert(k, i, {p[i - 1], 0 + p[n] * p[i - 1] -p[i - 1] * p[i - 1]});
ll val;
for (ll kk = k - 1; kk >= 0; kk --){
for (ll i = n; i > 0; i --){
auto P = query(kk + 1, i, p[i - 1]);
val = P.F - p[n] * p[i - 1], par[i][kk] = P.S;
insert(kk, i, {p[i - 1], val + p[n] * p[i - 1] -p[i - 1] * p[i - 1]});
}
hull[kk + 1].clear();
hull[kk + 1].shrink_to_fit();
}
cout << val << '\n';
int cur = 1;
for (int kk = 1; kk <= k; kk ++){
cur = par[cur][kk - 1];
cout << cur - 1 << " ";
}
cout << '\n';
}
