#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, k;
vector<ll> a, s;
vector<ll> dp_prev, dp_cur;
vector<vector<int>> parent;
void solve(int t, int l, int r, int optL, int optR) {
if (l > r) return;
int mid = (l + r) / 2;
pair<ll,int> best = {LLONG_MIN, -1};
for (int j = optL; j <= min(mid-1, optR); j++) {
ll val = dp_prev[j] + s[j] * (s[mid]-s[j]);
if (val > best.first) best = {val, j};
}
dp_cur[mid] = best.first;
parent[t][mid] = best.second;
int opt = best.second;
solve(t, l, mid-1, optL, opt);
solve(t, mid+1, r, opt, optR);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
a.assign(n+1,0); s.assign(n+1,0);
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++) s[i] = s[i-1]+a[i];
dp_prev.assign(n+1,0);
dp_cur.assign(n+1,0);
parent.assign(k+1, vector<int>(n+1,-1));
for(int t=1;t<=k;t++){
solve(t,1,n,0,n-1);
dp_prev = dp_cur;
}
ll answer = dp_prev[n];
// Reconstruct splits
vector<int> cuts;
int pos = n;
for(int t=k; t>=1; t--){
int j = parent[t][pos];
if(j > 0) cuts.push_back(j); // only actual splits
pos = j;
}
reverse(cuts.begin(), cuts.end());
// Output
cout << answer << "\n";
for(int i=0;i<(int)cuts.size();i++){
if(i>0) cout << " ";
cout << cuts[i];
}
cout << "\n";
}
