#include <bits/stdc++.h>
#define int long long
using namespace std;
double calc(pair<int, int> a, pair<int, int> b) {
return double(b.second-a.second)/double(a.first-b.first);
}
signed 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(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;
dq.push_back({{p[i], dp[1][i]-p[i]*p[i]}, i});
dp[0] = dp[1];
for(int j=i+1; j<=n; j++) {
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[1][j] = cx*m + c;
pair<int, int> l = {p[j], dp[0][j]-p[j]*p[j]};
bool mk = 0;
while(!dq.empty() && dq.back().first.first == p[j]) {
if(dq.back().first.second >= l.second) {
mk = 1;
break;
}
dq.pop_back();
}
while(!mk && dq.size() > 1 && calc(dq[dq.size()-2].first, dq.back().first) >= calc(dq.back().first, l)) dq.pop_back();
if(mk == 0) 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[1][n] << "\n";
for(auto i: ans) cout << i << " ";
}
