#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10, maxk = 200 + 5;
const long long inf = 1e14;
long long dp[2][maxn], s[maxn];
int t[maxk][maxn];
struct line {
long long a, b;
int i;
long long operator()(const long long &x) const { return a * x + b; }
bool checkfront(const line &rhs, const long long &x) const { return operator()(x) >= rhs(x); }
long double inter(const line &rhs) const { return 1.0 * (rhs.b - b) / (a - rhs.a); }
bool checkback(const line &rhs, const line &pivot) { return inter(pivot) <= rhs.inter(pivot); }
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n, k; cin >> n >> k;
for (int i = 1; i <= n; ++i) {
int a; cin >> a;
s[i] = s[i - 1] + a;
}
dp[0][0] = -inf;
for (int i = 1; i <= n; ++i) dp[0][i] = 0;
int cur = 1;
for (int i = 1; i <= k; ++i) {
// memset(dp[cur], 0, sizeof(dp[cur]));
fill(dp[cur], dp[cur] + maxn, -inf);
deque<line> dq; dq.push_back({ s[1], -s[1] * s[1], 1 });
// cout << "dp[" << i << "][" << 1 << "] = " << dp[cur][1] << endl;
for (int j = 2; j <= n; ++j) {
while (dq.size() >= 2 && dq[1].checkfront(dq[0], s[j])) dq.pop_front();
dp[cur][j] = dq.front()(s[j]);
// cout << "dp[" << i << "][" << j << "] = " << dp[cur][j] << endl;
t[i][j] = dq.front().i;
// cout << "t[" << i << "][" << j << "] = " << t[i][j] << endl;
line tmp = { s[j], dp[cur ^ 1][j] - s[j] * s[j], j };
while (dq.size() >= 2 && tmp.checkback(dq[dq.size() - 1], dq[dq.size() - 2])) dq.pop_back();
// if (dq.size() && dq.back().a == tmp.a && dq.back().b >= tmp.b) continue;
dq.push_back(tmp);
}
cur ^= 1;
}
/* int cur = 1; dp[0][0] = -inf;
for (int i = 1; i <= k; ++i) {
fill(dp[cur], dp[cur] + maxn, -inf);
for (int j = 1; j <= n; ++j) {
for (int p = 1; p < j; ++p) {
if (dp[cur ^ 1][p] + s[p] * (s[j] - s[p]) > dp[cur][j]) {
dp[cur][j] = dp[cur ^ 1][p] + s[p] * (s[j] - s[p]);
t[i][j] = p;
}
}
}
cur ^= 1;
} */
cout << dp[cur ^ 1][n] << endl;
stack<int> ans;
int now = n;
for (int i = k; i > 0; --i) {
ans.push(t[i][now]);
now = t[i][now];
}
while (ans.size()) cout << ans.top() << ' ', ans.pop(); cout << endl;
}
