/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using namespace std;
#define ln '\n'
#define INFi 1e9
#define INFll 1e18
#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#define myassert(Expr, Msg) ;
#endif
constexpr int upK = 201, upN = 100000 + 505;
size_t _n;
int _k;
int pa[upK][upN];
vector<ll> A, dp_prev, dp_cur;
vector<ll> pref;
inline void systemd() {
A.assign(_n + 1, 0);
dp_prev.assign(_n + 1, 0);
dp_cur.assign(_n + 1, 0);
pref.assign(_n + 2, 0);
}
ll cost(int l, int r) {
return (pref[r] - pref[l]) * (pref[_n] - pref[r]);
}
void calc(int &k, int l, int r, int optl, int optr) {
if (l > r)
return;
pair<ll, int> best = {-1, -1};
int mid = (l + r) >> 1;
myassert(optl <= optr, "WA: opt-left must be smaller or equal to opt-right");
dbg(make_pair(l, r));
dbg(make_pair(optl, optr));
dbg(mid);
for (int i = max(0, optl); i <= min(mid - 1, optr); i++) {
dbg(i);
best = max<pair<ll, int>>(best, make_pair(dp_prev[i] + cost(i, mid), i));
}
dbg(best);
ll &w = best.first;
int &opt = best.second;
dp_cur[mid] = w;
pa[k][mid] = opt;
calc(k, l, mid - 1, optl, opt);
calc(k, mid + 1, r, opt, optr);
}
char solve() {
if (!(cin >> _n >> _k))
return 1;
systemd();
for (size_t i = 1; i <= _n; i++) {
cin >> A[i];
}
for (size_t i = 1; i <= _n; i++) {
pref[i] = pref[i - 1] + A[i];
}
pref[_n + 1] = pref[_n];
for (size_t i = 1; i < _n; i++) {
dp_prev[i] = pref[i] * (pref[_n] - pref[i]);
}
dbg(dp_prev);
for (int _ = 1; _ < _k; _++) {
calc(_, 1, _n - 1, 1, _n- 1);
dp_prev.swap(dp_cur);
dbg(dp_prev);
}
ll mx = -INFll;
size_t id = 0;
for (size_t i = 1; i < _n; i++) {
if (mx < dp_prev[i]) {
mx = dp_prev[i];
id = i;
}
}
vector<int> ans;
for (int k = _k - 1; k >= 1; --k) {
ans.push_back(id);
id = pa[k][id];
}
ans.push_back(id);
cout << mx << ln;
reverse(ans.begin(), ans.end());
for (int &i : ans) {
cout << i << ' ';
}
#ifdef ONPC
#endif // ONPC
return 0;
}
// Attack on titan<3
signed main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
int t = 1e9;
// cin >> t;
for (int cases = 0; cases < t; cases++) {
if (solve())
break;
#ifdef ONPC
cerr << "__________\n";
#endif
}
}
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/
