#include <iostream>
#define int long long
using namespace std;
const int MAX_N = 1e5;
const int MAX_K = 200;
const int INF = (1LL << 60);
int a[MAX_N + 1], sp[MAX_N + 1], dp[MAX_N + 1][2];
int sol[MAX_N + 1][MAX_K + 1];
int n, k;
void divide(int k, int l, int r, int p, int q) {
if (p > q) {
return;
}
int mid = (p + q) / 2;
dp[mid][k & 1] = -INF;
int best = 0;
for (int i = l; i <= min(mid, r); i++) {
int kek = (sp[mid] - sp[i - 1]) * (sp[n] - sp[mid]);
if (dp[i - 1][(k & 1) ^ 1] + kek >= dp[mid][k & 1]) {
dp[mid][k & 1] = dp[i - 1][(k & 1) ^ 1] + kek;
best = i;
}
}
sol[mid][k] = best - 1;
divide(k, l, best, p, mid - 1);
divide(k, best, r, mid + 1, q);
}
signed main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sp[i] = sp[i - 1] + a[i];
}
k++;
for (int i = 1; i <= n; i++) {
dp[i][1] = sp[i] * (sp[n] - sp[i]);
}
for (int i = 2; i <= k; i++) {
divide(i, 1, n, 1, n);
}
cout << dp[n][k & 1] << "\n";
int aux = n;
for (int i = k; i >= 2; i--) {
cout << sol[aux][i] << " ";
aux = sol[aux][i];
}
return 0;
}
