#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const int N = (int)1e5 + 1;
const int K = 201;
int ans[K][N];
ll pre[N], dp[N], a[N];
struct Line {
ll m, c;
ll y(ll x) { return m * x + c; }
ld inter(Line l) { return (ld)(c - l.c) / (l.m - m); }
Line (ll M, ll C) { m = M, c = C; }
};
__int128_t rem(Line l, Line l1, Line l2) {
return ((__int128_t)(l1.c - l.c) * (__int128_t)(l1.m - l2.m) - (__int128_t)(l2.c - l1.c) * (__int128_t)(l.m - l1.m));
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) a[i] += a[i-1];
for (int x = 1; x <= k; x++) {
deque<pair<Line, int>> dq;
dq.emplace_back(Line(a[x-1], pre[x-1] - a[x-1] * a[x-1]), x-1);
for (int i = x; i <= n; i++) {
while (dq.size() > 1 && dq[0].first.y(a[i]) <= dq[1].first.y(a[i])) dq.pop_front();
dp[i] = dq[0].first.y(a[i]);
ans[x][i] = dq[0].second;
Line l = Line(a[i], -a[i] * a[i] + pre[i]);
while (dq.size() > 1 && rem(l, dq.back().first, dq[dq.size()-2].first) <= (__int128_t)0) dq.pop_back();
dq.emplace_back(l, i);
}
for (int i = 1; i <= n; i++) pre[i] = dp[i];
}
int t = n;
cout << dp[n] << '\n';
for (int i = k; i > 0; i--) {
cout << ans[i][t] << ' ';
t = ans[i][t];
}
}
