#include <bits/stdc++.h>
using namespace std;
#define nl endl
using ll = long long;
const ll inf = 1e18;
struct line {
ll m, b;
int idx;
line() : m(0), b(-inf), idx(-1) {}
line(ll m, ll b, int idx) : m(m), b(b), idx(idx) {}
ll operator * (const int &x) {
return m * x + b;
}
};
void solve() {
int n, k; cin >> n >> k;
vector<int> a(n);
for(auto &x : a) cin >> x;
vector<int> pref(n + 1), suf(n + 1);
for(int i = 0; i < n; i++) {
pref[i + 1] = pref[i] + a[i];
}
for(int i = n - 1; i >= 0; i--) {
suf[i] = suf[i + 1] + a[i];
}
vector<ll> dp(n + 1);
vector<vector<int>> p(n + 1, vector<int>(k, -1));
for(int j = 0; j < k; j++) {
vector<ll> ndp(n + 1, -inf);
deque<line> dq;
for(int i = 0; i <= n; i++) {
int x = -suf[i];
while(dq.size() >= 2 && dq[0] * x < dq[1] * x) {
dq.pop_front();
}
if(!dq.empty()) {
ndp[i] = dq[0] * x + pref[i] * 1LL * suf[i];
p[i][j] = dq[0].idx;
}
dq.push_back(line(pref[i], dp[i], i));
}
swap(dp, ndp);
}
int opt = -1;
for(int i = 0; i <= n; i++) {
if(opt == -1 || dp[opt] < dp[i]) {
opt = i;
}
}
cout << dp[opt] << nl;
for(int j = k - 1; j >= 0; j--) {
cout << opt << ' ';
opt = p[opt][j];
}
cout << nl;
}
/**
**/
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
