// - Art -
#include <bits/stdc++.h>
#define el cout << '\n'
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define REP(i, c) for (int i = 0, _c = (c); i < _c; ++i)
const int N = 1e5 + 7;
const int RANGE = 300;
template <class T1, class T2>
bool maximize(T1 &a, T2 b) {
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b) {
if (a > b) {a = b; return true;}
return false;
}
using namespace std;
int a[N], pre[N];
long long dp[N][2];
int where[N][202];
int sum(int l, int r) {
return pre[r] - pre[l - 1];
}
namespace naive {
long long dp[1002][202];
void solve(int n, int k) {
memset(dp, -0x3f, sizeof dp); // có thể có trường hợp sum(l,m)*sum(m+1,r)=0
dp[0][0] = 0;
FOR (x, 1, k + 1) FOR (i, 1, n) FOR (j, 1, i) {
if (maximize(dp[i][x], dp[j - 1][x - 1] + 1ll * sum(j, i) * sum(i + 1, n))) {
where[i][x] = j - 1;
}
}
cout << dp[n][k + 1], el;
int idx = n;
REV (i, k + 1, 2) {
cout << where[idx][i] << ' ';
idx = where[idx][i];
}
}
}
namespace heuristic {
#define f(x) (dp[(x) - 1][v] + 1ll * sum((x), i) * sum(i + 1, n))
void solve(int n, int k) {
bool u = 1, v = 0;
FOR (x, 1, k + 1) {
FOR (i, 1, n) {
dp[i][u] = -1e18;
int lo = 1, hi = i;
while (lo <= hi) {
if (hi - lo <= RANGE) {
FOR (j, lo, hi) {
if (maximize(dp[i][u], f(j))) {
where[i][x] = j - 1;
}
}
break;
}
int m1 = lo + (hi - lo) / 3;
int m2 = hi - (hi - lo) / 3;
long long f1 = f(m1), f2 = f(m2);
if (maximize(dp[i][u], f1)) {
where[i][x] = m1 - 1;
}
if (maximize(dp[i][u], f2)) {
where[i][x] = m2 - 1;
}
if (f1 < f2) {
lo = m1 + 1;
}
else {
hi = m2 - 1;
}
}
}
u ^= 1; v ^= 1;
}
cout << dp[n][v], el;
int idx = n;
REV (i, k + 1, 2) {
cout << where[idx][i] << ' ';
idx = where[idx][i];
}
}
}
namespace correct {
void solve(int n, int k) {
FOR (i, 1, n) {
dp[i][1] = 1ll * pre[i] * (pre[n] - pre[i]);
}
FOR (c, 2, k) {
auto calc = [&] (int j, long long x) {
return pre[j] * x + -1ll * pre[j] * pre[n] + dp[j][!(c & 1)];
};
auto m = [&] (int x, int y) {
return (double)(calc(x, 0) - calc(y, 0)) / (pre[y] - pre[x]);
};
deque<int> cht;
int sz = 0;
cht.emplace_back(c - 1); ++sz;
FOR (i, c, n) {
while (sz > 1 && calc(cht[0], pre[i]) <= calc(cht[1], pre[i])) {
cht.pop_front();
--sz;
}
dp[i][c & 1] = 1ll * pre[i] * (pre[n] - pre[i]) + calc(cht[0], pre[i]);
where[i][c] = cht[0];
while (sz > 0 && pre[cht[sz - 1]] == pre[i] && calc(cht[sz - 1], 0) <= calc(i, 0)) {
cht.pop_back(); --sz;
}
while (sz > 1 && m(cht[sz - 1], i) <= m(cht[sz - 1], cht[sz - 2])) {
cht.pop_back(); --sz;
}
cht.emplace_back(i); ++sz;
}
}
long long mx = 0, idx = -1;
FOR (i, k, n - 1) if (maximize(mx, dp[i][k & 1])) {
idx = i;
}
cout << mx, el;
REV (i, k, 1) {
cout << idx << ' ';
idx = where[idx][i];
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, k;
cin >> n >> k;
FOR (i, 1, n) {
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
if (n <= 1e3) {
naive::solve(n, k);
return 0;
}
if (n <= 1e4) {
heuristic::solve(n, k);
return 0;
}
correct::solve(n, k);
return 0;
}
