#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
using namespace std;
const int N = 1e5 + 5;
ll n, k, a[N], S[N], dp[N];
int P[N][202];
struct Line {
ll k, b, id;
ll vl(ll x) {
return k * x + b;
}
pair <ll , ll > intr(const Line& yo) {
ll one = yo.b - b;
ll two = k - yo.k;
if (two < 0) one *= -1, two *= -1;
return {one, two};
}
};
deque < Line > dq;
void insert(ll k, ll b, ll id) {
Line line = {k, b, id};
while (dq.size() > 1) {
Line linea = dq.end()[-1];
Line lineb = dq.end()[-2];
pair < ll , ll > A = lineb.intr(linea);
pair < ll , ll > B = linea.intr(line);
if (A.F * B.S >= B.F * A.S) dq.pop_back();
else break;
}
dq.push_back(line);
}
pair < ll , int > qr(int x) {
while (dq.size() > 1) {
if (dq[0].vl(x) <= dq[1].vl(x)) dq.pop_front();
else break;
}
return {dq[0].vl(x), dq[0].id};
}
main () {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
S[i] = S[i - 1] + a[i];
}
Line bs = {0, 0, 0};
dq.push_front(bs);
for (int st = 1; st <= k; ++st) {
for (int i = st; i <= n; ++i) {
pair < ll , int > lol = qr(S[i]);
P[i][st] = lol.S;
dp[i] = lol.F + (S[n] - S[i]) * S[i];
}
while (dq.size()) dq.pop_back();
dq.push_front(bs);
for (int j = st; j <= n; ++j) {
insert(S[j], dp[j] - S[n] * S[j], j);
}
}
vector < int > ans;
ll idx = k, res = dp[k];
for (int i = k + 1; i <= n; ++i) {
if (dp[i] > res) {
res = dp[i];
idx = i;
}
}
cout << res << "\n";
for (int i = k; i >= 1; --i) {
ans.push_back(idx);
idx = P[idx][i];
}
reverse(ans.begin(), ans.end());
for (int i = 0; i < ans.size(); ++i) {
cout << ans[i] << " ";
}
}
