#include <bits/stdc++.h>
using namespace std;
double calc(pair<int, int> a, pair<int, int> b) {
return double(b.second-a.second)/double(a.first-b.first);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, k;
cin >> n >> k;
vector<int> arr(n+2, 0), p(n+2, 0), ans;
vector<vector<int>> dp(k+2, vector<int>(n+2, 0)), path(k+2, vector<int>(n+2, 0));
for(int i=1; i<=n; i++) {
cin >> arr[i];
p[i] = p[i-1] + arr[i];
}
for(int i=1; i<=k; i++) {
deque<pair<pair<int, int>, int>> dq;
for(int j=1; j<=i; j++) {
while(dq.size() > 1 && calc(dq[dq.size()-2].first, dq.back().first) >= calc(dq.back().first, {p[j], dp[i-1][j]})) dq.pop_back();
dq.push_back({{p[j], dp[i-1][j]-p[j]*p[j]}, j});
}
for(int j=i+1; j<=n; j++) {
if(p[j] == p[j-1]) continue;
int cx = p[j];
while(dq.size() > 1 && calc(dq[0].first, dq[1].first) <= cx) dq.pop_front();
auto [m, c] = dq.front().first;
path[i][j] = dq.front().second;
dp[i][j] = cx*m + c;
pair<int, int> l = {p[j], dp[i-1][j]-p[j]*p[j]};
while(dq.size() > 1 && calc(dq[dq.size()-2].first, dq.back().first) >= calc(dq.back().first, l)) dq.pop_back();
dq.push_back({l, j});
}
}
int ck = k, cidx = n;
while(ck > 0) {
ans.push_back(path[ck][cidx]);
cidx = path[ck][cidx];
ck--;
}
sort(ans.begin(), ans.end());
cout << dp[k][n] << "\n";
for(auto i: ans) cout << i << " ";
}
