// 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;
int par;
};
vector<line> dq;
int ptr = 0;
bool bad(const line& l1, const line& l2, const line& l3) {
return (__int128_t)(l1.b - l2.b) * (l3.a - l2.a) >= (__int128_t)(l2.b - l3.b) * (l2.a - l1.a);
}
void add(ll a, ll b, int i) {
line nw = {a, b, i};
while (dq.size() > ptr) {
if (dq.back().a == nw.a) {
if (dq.back().b >= nw.b) return;
dq.pop_back();
} else {
break;
}
}
while (dq.size() - ptr >= 2 && bad(dq[dq.size() - 2], dq.back(), nw)) {
dq.pop_back();
}
dq.push_back(nw);
}
pair<ll, int> qr(ll x) {
assert(dq.size() > ptr);
while (dq.size() - ptr >= 2) {
ll val1 = dq[ptr].a * x + dq[ptr].b;
ll val2 = dq[ptr + 1].a * x + dq[ptr + 1].b;
if (val1 <= val2) {
ptr++;
} else {
break;
}
}
return {dq[ptr].a * x + dq[ptr].b, dq[ptr].par};
}
};
const int maxn = 1e5 + 10;
int n, k;
ll pref[maxn];
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);
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);
}
dp = nxtdp;
}
cout << dp[n] << '\n';
pair<int, int> sth = {n, k};
for(int i=1; i<k; ++i){
int nxt = trace[sth.fi][sth.se];
cout << nxt << ' ';
sth = {nxt, sth.se - 1};
}
}
signed main(){
// freopen("inp.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
