#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const long long inf = 4e18;
int n, m;
long long pref[N];
long long dp[N], new_dp[N];
int g[233][N];
void solve(int ph, int L, int R, int x, int y) {
if (L > R) {
return;
}
long long mx = -inf;
int bid = -1;
int cur = (L + R) >> 1;
for (int i = x; i <= min(y, cur - 1); i++) {
if (dp[i] == -inf) {
continue;
}
long long c = dp[i] + (pref[cur] - pref[i]) * pref[i];
if (c > mx) {
mx = c;
bid = i;
}
}
new_dp[cur] = mx;
g[ph][cur] = bid;
solve(ph, L, cur - 1, x, bid);
solve(ph, cur + 1, R, max(x, bid), y);
}
void print(int x, int y) {
if (x == 0) {
assert(y == 0);
return;
}
print(x - 1, g[x][y]);
if (x != m + 1) {
printf("%d ", y);
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
pref[i + 1] = pref[i] + x;
}
fill(dp + 1, dp + n + 1, -inf);
for (int i = 0; i < m + 1; i++) {
solve(i + 1, 0, n, 0, n);
copy(new_dp, new_dp + n + 1, dp);
}
printf("%lld\n", dp[n]);
print(m + 1, n);
printf("\n");
return 0;
}
