#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll pref[100100];
struct line {
ll m, c, idx;
};
struct CHT {
deque<line> dq;
int p;
void clear() {
while (!dq.empty()) dq.pop_back();
p = 0;
}
long double intercept(line x, line y) {
long double ans = x.c - y.c;
ans /= y.m - x.m;
return ans;
}
bool replace(line x, line y, line z) {
return (x.c - y.c) * (z.m - x.m) >= (x.c - z.c) * (y.m - x.m);
}
void add(line x) {
while (dq.size() > 1 && replace(dq[dq.size() - 2], dq.back(), x)) {
dq.pop_back();
}
dq.push_back(x);
}
line query(ll x) {
p = min(p, (int)dq.size() - 1);
while (p < (int)dq.size() - 1 && intercept(dq[p], dq[p + 1]) < x) p++;
return dq[p];
}
} cht;
ll dp[2][100100];
int p[201][100001];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, k;
cin >> n >> k;
for (int i = 1;i <= n;i++) {
int t;
cin >> t;
pref[i] = pref[i - 1] + t;
}
/*
dp[i][j] = max[l]( dp[i-1][l] + (pref[j] - pref[l]) * (pref[n] - pref[j]))
= max[l]( dp[i-1][l] + pref[j] * pref[n] - pref[l]*pref[n]
- pref[j]*pref[j] + pref[l]*pref[j-1])
m = pref[l], c = -pref[l] * pref[n] + dp[i-1][l]
x = pref[j]
*/
memset(dp, 0xc0, sizeof dp);
dp[0][0] = 0;
for (int i = 1;i <= k;i++) {
cht.clear();
int now = i & 1, prev = 1 - now;
memset(dp[now], 0xc0, sizeof dp[now]);
cht.add({ pref[i - 1], -pref[i - 1] * pref[n] + dp[prev][i - 1] , i - 1 });
for (int j = i;j < n;j++) {
line t = cht.query(pref[j]);
dp[now][j] = t.m * pref[j] + t.c - pref[j] * pref[j] + pref[j] * pref[n];
cht.add({ pref[j], -pref[j] * pref[n] + dp[prev][j] , j });
p[i][j] = t.idx;
}
}
int idx = 0;
ll mx = 0;
for (int j = k;j < n;j++) {
if (dp[k & 1][j] > mx) {
mx = dp[k & 1][j];
idx = j;
}
}
cout << mx << '\n';
stack<int> ans;
int now = k;
while (idx != 0) {
ans.push(idx);
idx = p[now--][idx];
}
while (!ans.empty()) {
cout << ans.top() << ' ';
ans.pop();
}
return 0;
}
