#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
typedef string str;
const int N = 1e5 + 1, K = 201;
int n, k;
ll a[N], pref[N];
vector <ll> dp_old(N), dp_new(N);
int p[N][K], v;
ll get(int l, int r) {
return (pref[r] - pref[l - 1]) * (pref[n] - pref[r]);
}
void solve(int l, int r, int opt_l, int opt_r) {
if (l > r) {
return;
}
int mid = (l + r) >> 1;
pair <ll, int> best = {-1, -1};
for (int i = opt_l; i <= min(mid - 1, opt_r); ++i) {
best = max(best, {dp_old[i] + get(i + 1, mid), i});
}
dp_new[mid] = best.first;
int opt = best.second;
p[mid][v] = opt;
solve(l, mid - 1, opt_l, opt);
solve(mid + 1, r, opt, opt_r);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
}
for (int i = 1; i <= n; ++i) {
dp_old[i] = get(1, i);
dp_new[i] = get(1, i);
}
for (int i = 2; i <= k; ++i) {
v = i;
solve(i, n, 1, n);
dp_old = dp_new;
}
ll ans = -1;
int j = -1;
for (int i = 1; i <= n; ++i) {
if (dp_new[i] > ans) {
ans = dp_new[i];
j = i;
}
}
vector <int> arr;
for (int i = k; i >= 1; --i) {
arr.push_back(j);
j = p[j][i];
}
reverse(arr.begin(), arr.end());
cout << ans << '\n';
for (int i : arr) {
cout << i << ' ';
}
}
