#include <bits/stdc++.h>
using namespace std;
void just_do_it();
int main() {
#ifdef KAMIRULEZ
freopen("kamirulez.inp", "r", stdin);
freopen("kamirulez.out", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
just_do_it();
return 0;
}
const long long inf = 1e18L + 20;
const int maxN = 1e5 + 20;
const int maxK = 2e2 + 20;
int a[maxN];
long long pref[maxN];
long long cur_dp[maxN];
long long nxt_dp[maxN];
int best[maxN][maxK];
struct line {
long long a = 0;
long long b = 0;
line() {};
line(long long _a, long long _b): a(_a), b(_b) {};
long long eval(long long x) {
return a * x + b;
};
};
long long floor_div(long long x, long long y) {
return (x / y) - ((x ^ y) < 0 && x % y);
}
long long inter(line L1, line L2) {
return floor_div(L2.b - L1.b, L1.a - L2.a);
}
struct cht {
vector<pair<int, line>> Q;
int pt = 0;
void clear() {
Q.clear();
pt = 0;
}
void add(int id, line L) {
while ((int)Q.size() >= 2) {
if (Q.back().second.a == L.a) {
if (Q.back().second.b >= L.b) {
return;
}
else {
Q.pop_back();
}
}
else if (inter(Q.end()[-2].second, Q.back().second) >= inter(Q.back().second, L)) {
Q.pop_back();
}
else {
break;
}
}
if (!Q.empty()) {
if (Q.back().second.a == L.a) {
if (Q.back().second.b >= L.b) {
return;
}
else {
Q.pop_back();
}
}
}
Q.emplace_back(id, L);
}
pair<int, long long> get(long long x) {
assert(!Q.empty());
pt = min(pt, (int)Q.size() - 1);
while (pt < (int)Q.size() - 1 && Q[pt].second.eval(x) < Q[pt + 1].second.eval(x)) {
pt++;
}
return make_pair(Q[pt].first, Q[pt].second.eval(x));
}
} CHT;
void just_do_it() {
int N, K;
cin >> N >> K;
for (int i = 1; i <= N; i++) {
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
}
CHT.add(0, line(0, 0));
for (int j = 1; j <= K + 1; j++) {
for (int i = 1; i <= N; i++) {
if (j <= i) {
auto p = CHT.get(pref[i]);
best[i][j] = p.first;
nxt_dp[i] = p.second + pref[i] * (pref[N] - pref[i]);
}
if (j > 0 && j - 1 <= i) {
CHT.add(i, line(pref[i], cur_dp[i] - pref[i] * pref[N]));
}
}
swap(cur_dp, nxt_dp);
CHT.clear();
}
cout << cur_dp[N] << '\n';
int cur = N;
for (int i = K + 1; i >= 2; i--) {
cout << (cur = best[cur][i]) << " ";
}
}
