#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll neginf = -1e18;
struct Line {
ll m, c;
int cutidx = 0;
ll operator()(ll x) {return m*x+c;}
Line(ll _m, ll _c): m(_m), c(_c) {}
};
ll floordiv(ll a, ll b) {
return a/b - ((a^b) < 0 && a%b);
}
bool bruh(Line old1, Line old2, Line toins) {
//check if u should del or not
return floordiv(toins.c - old1.c, old1.m - toins.m) <= floordiv(old1.c - old2.c, old2.m - old1.m);
}
int n, k;
ll qs[200005];
ll dp[200005][2];
int par[20005][205];
void rec(int x, int k) {
if(x == 0) return ;
rec(par[x][k], k-1);
if(par[x][k]) cout << par[x][k] << ' ';
}
int main() {
cin.tie(0) -> sync_with_stdio(0);
cin >> n >> k;
for(int i=1;i<=n;i++) {
cin >> qs[i];
qs[i] += qs[i-1];
}
for(int ck=2;ck<=k+1;ck++) {
for(int i=0;i<=n;i++) dp[i][ck&1] = neginf;
deque<Line> deq;
for(int ci=ck-1;ci<n;ci++) {
Line toins(qs[ci], dp[ci][(ck&1)^1] - qs[ci]*qs[ci]); toins.cutidx = ci;
while(deq.size() > 1 && bruh(deq[deq.size()-2], deq.back(), toins)) deq.pop_back();
deq.emplace_back(toins);
//calculate for ci+1
while(deq.size() > 1 && deq[0](qs[ci+1]) <= deq[1](qs[ci+1])) deq.pop_front();
dp[ci+1][ck&1] = deq[0](qs[ci+1]);
par[ci+1][ck] = deq[0].cutidx;
}
}
cout << dp[n][(k&1)^1] << '\n';
rec(n, k+1);
}
