#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
// cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int n, k;
cin >> n >> k;
k++;
vector<ll> vi(n);
for (auto &a : vi) cin >> a;
for (int i = 1; i < n; i++) vi[i] += vi[i - 1];
// [..)
auto qry = [&](int l, int r) {
if (r == 0) return 0ll;
if (l == 0) return vi[r - 1];
return vi[r - 1] - vi[l - 1];
};
vector<vector<ll>> dp(2, vector<ll>(n + 1, -1e18));
vector<vector<int>> bef(k + 1, vector<int>(n + 1, -1));
dp[0][0] = 0;
for (int div = 1; div <= k; div++) {
queue<array<int, 4>> qai;
qai.push({1, n, 0, n - 1});
int cur = div % 2, other = 1 - div % 2;
for (int i = 0; i < n + 1; i++) dp[cur][i] = -1e18;
while (!qai.empty()) {
auto [l, r, bl, br] = qai.front();
qai.pop();
if (l > r) continue;
int mid = (l + r) / 2;
assert(bl < mid);
int bestin = bl;
dp[cur][mid] = dp[other][bl] + qry(0, bl) * qry(bl, mid);
for (int i = bl + 1; i <= br && i < mid; i++) {
ll x = dp[other][i] + qry(0, i) * qry(i, mid);
if (x > dp[cur][mid]) {
dp[cur][mid] = x;
bestin = i;
}
}
bef[div][mid] = bestin;
qai.push({l, (l + r) / 2 - 1, bl, bestin});
qai.push({(l + r) / 2 + 1, r, bestin, br});
}
// for (auto a : dp[div]) cout << a << ' ';
// cout << "\n";
}
// for (auto a : bef) {
// for (auto b : a) cout << b << " ";
// cout << "\n";
// }
cout << dp[k % 2][n] << "\n";
int cur = n;
for (int i = k; i > 1; i--) {
cout << bef[i][cur] << " ";
cur = bef[i][cur];
}
cout << "\n";
}
