#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
const int N = 1e5;
const int K = 2e2;
const ll INF = 1e18;
int n, k;
ll a[N+2], sum[N+2];
ll dp[N+5][K+5], bt[N+5][K+5];
struct line {
ll m, c, id;
ll operator ()(ll x) {
return m*x+c;
}
};
struct convexHull {
int sz;
vector<line> v;
void reset() {
v.clear();
sz = 0;
}
bool greaterFrac(ld a, ld b, ld c, ld d) {
return a/b >= c/d;
}
bool isBad(line a, line b, line c) {
// (c1-c2)/(m2-m1) >= (c2-c3)/(m3-m2)
return greaterFrac(a.c-b.c,b.m-a.m,b.c-c.c,c.m-b.m);
}
void insert(ll m, ll c, int id) {
line x = {m,c,id};
while (sz >= 2 && isBad(v[sz-2],v[sz-1],x)) {
v.pop_back(); sz--;
}
v.push_back(x); sz++;
}
ii query(ll x) {
ll ret = -INF, id = -1;
for (int l = 0, r = sz-1; l <= r; ) {
int mid = (l+r)/2;
if (ret < v[mid](x)) {
ret = v[mid](x);
id = v[mid].id;
}
if (mid+1 < sz && v[mid+1](x) > v[mid](x)) l = mid+1;
else r = mid-1;
}
return {ret,id};
}
} ch;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> k; k++;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i-1]+a[i];
}
for (int i = 2; i <= k; i++) {
ch.reset();
for (int j = i; j <= n; j++) {
ch.insert(sum[j-1],dp[j-1][i-1]-sum[j-1]*sum[j-1],j-1);
ii x = ch.query(sum[j]);
dp[j][i] = x.fi;
bt[j][i] = x.se;
}
}
vector<int> res;
for (int i = n, j = k; i >= 1; i = bt[i][j], j--) {
res.push_back(bt[i][j]);
}
sort(res.begin(),res.end());
cout << dp[n][k] << '\n';
for (int i = 1; i < res.size(); i++) {
if (i != 1) cout << ' ';
cout << res[i];
}
cout << '\n';
return 0;
}
