#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define X first
#define Y second
#define sep ' '
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl;
const ll MAXN = 1e5 + 10;
const ll INF = 8e18;
int wtf[202][MAXN];
ll dp[2][MAXN], ans, A[MAXN], n, s, tans, k, ptr;
vector<pair<pll, pll>> cht;
inline ll f(pll a, pll b) {
if (a.X == b.X) return (a.Y <= b.Y ? -INF : INF);
if (a.X < b.X) swap(a, b);
return (b.Y - a.Y + (b.Y > a.Y ? (a.X - b.X - 1) : 0)) / (a.X - b.X);
}
inline void add(int ind, ll ml, ll cl) {
pll a = {ml, cl};
while (!cht.empty()) {
ll x = f(cht.back().Y, a);
if (x <= cht.back().X.X) cht.pop_back();
else {
cht.push_back({{x, ind}, a});
break;
}
}
if (cht.empty())
cht.push_back({{-INF, ind}, a});
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> k;
k++;
for (int i = 1; i <= n; i++) {
cin >> A[i];
tans -= A[i];
}
// ans -= sigma C(2, F[i])
// ans -= F[i] * (F[i] - 1) / 2
// tans += F[i] * F[i] - F[i]
for (int c = 1; c <= k; c++) {
int ind = c & 1;
s = 0;
cht.clear();
ptr = 0;
add(0, 0, 0);
for (int i = 1; i <= n; i++) {
s += A[i];
while (ptr < int(cht.size()) - 1 && cht[ptr + 1].X.X <= s) ptr++;
dp[ind][i] = s * s - (cht[ptr].Y.X * s + cht[ptr].Y.Y);
wtf[c][i] = cht[ptr].X.Y;
if (c > 1) add(i, 2 * s, -(dp[ind ^ 1][i] + s * s));
}
}
tans += dp[k & 1][n];
cout << s * (s - 1) / 2 - tans / 2 << endl;
vector<int> vec;
int v = n;
while (k > 1)
vec.push_back(v = wtf[k--][v]);
reverse(all(vec));
for (int e : vec)
cout << e << sep;
cout << endl;
return 0;
}
