#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll s[100001];
ll dp[201][100001];
int par[201][100001];
double slope(int p, int x, int y) { // x > y
if(s[x] == s[y])
return 1e9;
return (double) (dp[p-1][y] - dp[p-1][x] - s[y] * s[y] + s[x] * s[x]) / (s[x] - s[y]);
}
int main() {
int n, k; cin >> n >> k;
s[0] = 0;
for(int i = 1; i <= n; i++) {
cin >> s[i];
s[i] += s[i-1];
}
dp[0][0] = -1e15;
par[0][0] = -1;
for(int i=1;i<=n;i++) {
dp[0][i] = 0;
par[0][i] = -1;
}
for(int p=1;p<=k;p++) {
deque<int> q;
dp[p][0] = -1e15;
for(int i=1;i<=n;i++) {
bool found = false;
if(i<=p) {
dp[p][i] = -1e15;
par[p][i] = -1;
found = true;
}
while(q.size()>1 && slope(p, q[1], q[0])<=s[i])
q.pop_front();
if(!found) {
int j = q.front();
dp[p][i] = dp[p-1][j]+(s[i]-s[j])*1LL*s[j];
par[p][i] = j;
}
while(q.size()>1&&slope(p, q[q.size()-1], q[q.size()-2])>slope(p, i, q[q.size()-1]))
q.pop_back();
if(i>=p)
q.push_back(i);
}
}
vector<int> ans;
int curr =n;
for(int p=k;p>=1;p--) {
ans.push_back(par[p][curr]);
curr = par[p][curr];
}
cout << dp[k][n] << "\n";
for(auto &a : ans) cout << a << " ";
}
