#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lll = __int128;
using vint = vector<int>;
using vll = vector<ll>;
using pint = pair<int, int>;
using vpint = vector<pint>;
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a)-1; i >= (b); i--)
const ll INF = 2e18;
struct Line {
int i;
ll m, c;
ll eval(ll x) { return m*x + c; }
};
bool is_bad(Line l1, Line l2, Line l3) {
return (lll)(l2.c - l1.c) * (l2.m - l3.m) <= (lll)(l2.m - l1.m) * (l2.c - l3.c);
}
void solve() {
int n, k; cin >> n >> k;
vint a(n); rep(i, n) cin >> a[i];
vint prefix(n);
rep(i, n) prefix[i] = i == 0 ? a[i] : a[i] + prefix[i-1];
vint suffix(n);
rrep(i, n) suffix[i] = i == n-1 ? 0 : a[i+1] + suffix[i+1];
vector<ll> p_dp(n-1, -INF), c_dp(n-1, -INF);
vector<vint> dp_i(k, vint(n-1));
rep(l, k) {
if (l == 0) rep(i, n-1) c_dp[i] = (ll)prefix[i]*suffix[i];
else {
deque<Line> dq;
rep(i, n-1) {
if (i > 0 && p_dp[i-1] != -INF) {
Line n_line = {i-1, -prefix[i-1], p_dp[i-1]};
while (dq.size() >= 2 && is_bad(dq[sz(dq)-2], dq.back(), n_line)) dq.pop_back();
dq.push_back(n_line);
}
if (!dq.empty()) {
ll x = suffix[i];
while (dq.size() >= 2 && dq[0].eval(x) <= dq[1].eval(x)) dq.pop_front();
c_dp[i] = (ll)prefix[i] * suffix[i] + dq[0].eval(x);
dp_i[l][i] = dq[0].i;
}
}
}
p_dp = c_dp;
c_dp.assign(n-1, -INF);
}
ll res = -INF, res_i = -1;
FOR(i, k-1, n-1) if (res < p_dp[i]) res = p_dp[i], res_i = i;
cout << res << endl;
vint pos(k);
rrep(i, k)
pos[i] = res_i, res_i = dp_i[i][res_i];
rep(i, k) cout << pos[i]+1 << " ";
cout << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
