#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (1e5)+1, K = 201;
struct MaxHull {
struct line {
ll m, c;
int i;
ll getVal(ll x) { return m*x + c; };
};
int idx = 0;
vector<line> lines;
bool bad(line l1, line l2, line l3) {
assert(l1.m <= l2.m && l2.m <= l3.m);
return (l3.c-l1.c)*(l1.m-l2.m) <= (l2.c-l1.c)*(l1.m-l3.m);
}
void update(ll m, ll c, int i) {
line l = {m, c, i};
while(lines.size() > 3 && bad(lines[lines.size()-2], lines[lines.size()-1], l)) lines.pop_back();
while(!lines.empty() && lines.back().m == l.m && lines.back().c <= l.c) lines.pop_back();
lines.push_back(l);
}
pair<ll, int> query(ll x) {
assert(!lines.empty());
while(idx+1 < lines.size() && lines[idx+1].getVal(x) >= lines[idx].getVal(x)) ++idx;
return make_pair(lines[idx].getVal(x), lines[idx].i);
}
} hull;
int n, k, a[N], trace[K][N];
ll ans, s[N], dp[2][N];
vector<int> order;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = s[i-1] + a[i];
}
int curr = 0;
for(int cnt = 1; cnt <= k; cnt++, curr ^= 1) {
memset(dp[curr], 0, sizeof(dp[curr]));
hull.idx = 0;
hull.lines.clear();
// hull.update(0, 0, 0); // can do this to get rid of third line in update function
hull.update(s[cnt], dp[curr^1][cnt] - s[cnt]*s[cnt], cnt);
for(int i = cnt+1; i <= n; i++) {
tie(dp[curr][i], trace[cnt][i]) = hull.query(s[i]);
hull.update(s[i], dp[curr^1][i] - s[i]*s[i], i);
}
}
for(int cnt = k, i = n; cnt >= 1; i = trace[cnt][i], cnt--) order.push_back(trace[cnt][i]);
reverse(order.begin(), order.end());
cout << dp[curr^1][n] << endl;
for(int i: order) cout << i << ' ';
}
