#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int MAXN = 1e5+5;
//ll dp[MAXN][205];
vector<ll> new_dp(MAXN), dp(MAXN);
ll in[MAXN], pref[MAXN];
int cut[MAXN][205];
ll n, k;
void solve(int l, int r, int optl, int optr, int k)
{
if(l > r)
return;
int mid = (l + r) / 2;
pair<ll, ll> best = {-1e18, -1};
for(int i = optl; i <= min(mid, optr); i++)
{
best = max(best, {dp[i-1] + (pref[mid] - pref[i - 1]) * (pref[n] - pref[mid]), i});
}
new_dp[mid] = best.first;
int opt = best.second;
cut[mid][k] = opt;
solve(l, mid - 1, optl, opt, k);
solve(mid + 1, r, opt, optr, k); // From the monotonicity: opt(i, j) <= opt(i, j + 1); in which case opt is our point where we split our l, r range to get the sum most valuable. Since right side of the sum increase as we increase j, so opt side will also increase/stay the same compared with a lower j (to balance the sum between left side and right side) so opt(i, j) <= opt(i, j + 1) holds.
}
int main()
{
//ll n, k;
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> in[i];
pref[i] = pref[i - 1] + in[i];
//dp[i][0] = pref[i];
}
for(int i = 1; i <= k; i++)
{
solve(1, n-1, 1, n-1, i);
dp = new_dp;
}
ll ans = 0;
int curr = 0;
for(int i = 1; i <= n - 1; i++) {
ans = max(ans, dp[i]); // dp[i][k] maximum points by last splitting a range which ends with i.
if(ans == dp[i])
curr = i;
}
cout << ans << "\n";
vector<int> moves;
moves.push_back(curr);
for(int i = k; i > 1; i--)
{
moves.push_back(cut[curr][i] - 1);
curr = cut[curr][i] - 1;
}
reverse(moves.begin(), moves.end());
for(int e : moves)
cout << e << " ";
cout << "\n";
}
