#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10, maxk = 200 + 5;
long long dp[2][maxn], s[maxn];
int t[maxk][maxn];
struct line {
long long a, b;
int i;
long long operator()(const long long &x) const { return a * x + b; }
bool checkfront(const line &rhs, const long long &x) const { return (*this)(x) >= rhs(x); }
long long inter(const line &rhs) const { return (rhs.b - b) / (a - rhs.a); }
bool checkback(const line &rhs, const line &pivot) { return inter(pivot) >= rhs.inter(pivot); }
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n, k; cin >> n >> k;
for (int i = 1; i <= n; ++i) {
int a; cin >> a;
s[i] = s[i - 1] + a;
}
dp[0][0] = 0;
int cur = 1;
for (int i = 1; i <= k; ++i) {
memset(dp[cur], 0, sizeof(dp[cur]));
deque<line> dq; dq.push_back({ 0, dp[cur ^ 1][0], 0 });
for (int j = 1; j <= n; ++j) {
while (dq.size() >= 2 && dq[1].checkfront(dq[0], s[j])) dq.pop_front();
dp[cur][j] = dq.front()(s[j]);
t[i][j] = dq.front().i;
line tmp = { s[j], dp[cur ^ 1][j] - s[j] * s[j], j };
while (dq.size() >= 2 && tmp.checkback(dq[dq.size() - 1], dq[dq.size() - 2])) dq.pop_back();
dq.push_back(tmp);
}
cur ^= 1;
}
cout << dp[cur ^ 1][n] << endl;
stack<int> ans;
int now = n;
for (int i = k; i > 0; --i) {
ans.push(t[i][now]);
now = t[i][now];
}
while (ans.size()) cout << ans.top() << ' ', ans.pop(); cout << endl;
}
