#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 dp[maxN][maxK];
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;
};
};
struct CHT {
vector<pair<int, line>> Q;
void add(int id, line L) {
Q.emplace_back(id, L);
}
pair<int, long long> get(long long x) {
long long mx = -inf;
int best = -1;
for (auto p: Q) {
long long cur = p.second.eval(x);
if (cur > mx) {
mx = cur;
best = p.first;
}
}
return make_pair(best, mx);
}
};
CHT C[maxK];
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];
}
C[0].add(0, line(0, 0));
for (int i = 1; i <= N; i++) {
for (int j = min(i, K + 1); j >= 1; j--) {
auto p = C[j - 1].get(pref[i]);
best[i][j] = p.first;
dp[i][j] = p.second + pref[i] * (pref[N] - pref[i]);
C[j].add(i, line(pref[i], dp[i][j] - pref[i] * pref[N]));
}
}
cout << dp[N][K + 1] << '\n';
int cur = N;
for (int i = K + 1; i >= 2; i--) {
cout << (cur = best[cur][i]) << " ";
}
}
