#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define int long long
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];
}
auto bad = [&](line l1, line l2, line l3) {
// intersection(l1, l2) >= intersection(l2, l3)
return (__int128)(l2.b - l1.b) * (l2.m - l3.m) >= (__int128)(l3.b - l2.b) * (l1.m - l2.m);
};
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;
}
line cur(pref[i], dp[i], i);
while(dq.size() >= 2 && bad(dq[dq.size() - 2], dq.back(), cur)) dq.pop_back();
dq.push_back(cur);
}
swap(dp, ndp);
// for(int i = 0; i <= n; i++) {
// cout << dp[i] << ' ';
// }
// cout << nl;
}
int opt = -1;
for(int i = 1; i <= n; i++) {
if(opt == -1 || dp[opt] < dp[i]) {
opt = i;
}
}
// opt = -1;
// while(opt == -1);
cout << dp[opt] << nl;
for(int j = k - 1; j >= 0; j--) {
// while(opt == -1);
cout << opt << ' ';
opt = p[opt][j];
}
cout << nl;
}
/**
**/
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
